连通分量算法
① 设计一个算法,求无向图G(采用邻接表存储)的连通分量的个数
int Count(Graph G)
{
int count=0;
for(v=0;v<G.vexnum;++v) visited[v]=false; //初始化每个节点的被访问标记
for(v=0;v<G.vexnum;++v)
{
if(!visited[v])
{
DFS(G,v);
count++;
}
}
return count;
}
void DFS(Graph G, int)
{
visited[v]=true;
for(w=FirstAdjVex(G,v); w; w=NextAgjVex(G,v,w))
{
if(!visited[w]) DFS(G,w)
}
}
② 请问如何求(有向/无向)图的强连通分量，还有，基础一点，怎么求有几个连通图啊
求强连通分量的算法有tarjan和kosaraju 两种算法
相较之下 tarjan写起来比较简单 Kosaraju比较麻烦
但是想起来 Kosaraju比较简单
其他求强连通分量的算法 要是还有的话 估计就是需要更高深的数据结构的算法了
建议还是学下tarjan 因为他可以帮你做很多事 比如 求桥 求割点 缩环 而且写起来也很简单
连通图的求法可以直接DFS 每次DFS到一个点 就把它记录成已到达 然后继续向下搜索 每次DFS就可以求出一个连通图
附上tarjan的代码
var
next,head,point:array[1..1000] of longint;
time,tot,i,j,n,m,x,y,t:longint;
v:array[1..10000] of byte;
f,z,q:array[1..1000] of longint;
low,rea:array[1..10000] of longint;
function min(x,y:longint):longint;
begin
if x<y then exit(x) else exit(y);
end;
procere add(x,y:longint);
begin
inc(tot);
next[tot]:=head[x];
head[x]:=tot;
point[tot]:=y;
end;
procere dfs(x:Longint);
var
i,j:longint;
begin
inc(time);
low[x]:=time;
rea[x]:=time;
v[x]:=1;
inc(t);
z[t]:=x;
j:=head[x];
while j<>0 do
begin
if v[point[j]]=0 then dfs(point[j]);
if v[point[j]]<2 then low[x]:=min(low[point[j]],low[x]);
j:=next[j];
end;
if low[x]=rea[x] then
begin
inc(tot);
while z[t+1]<>x do
begin
inc(q[tot]);
f[z[t]]:=tot;
v[z[t]]:=2;
dec(t);
end;
end;
end;
begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y);
add(x,y);
end;
tot:=0; time:=0;
for i:=1 to n do
if v[i]=0 then dfs(i);
//writeln(tot);
for i:=1 to n do
if q[f[i]]<>1 then writeln('T') else writeln('F');
end.
③ 广度优先算法和深度优先算法哪个可以求无向图的所有连通分量，具体什么原理
你好，广度优先和深度优先都可以求出无向图的所有连通分量，他们的原理都是遍历，一个是先按广度进行遍历，另外一个是先按深度进行遍历。
④ 强连通分量的Kosaraju算法思路
这个算法可以说是最容易理解，最通用的算法，其比较关键的部分是同时应用了原图G和反图GT。步骤1：先用对原图G进行深搜形成森林(树)，步骤2：然后任选一棵树对其进行深搜(注意这次深搜节点A能往子节点B走的要求是EAB存在于反图GT)，能遍历到的顶点就是一个强连通分量。余下部分和原来的森林一起组成一个新的森林，继续步骤2直到
没有顶点为止。
改进思路：
当然，基本思路实现起来是比较麻烦的(因为步骤2每次对一棵树进行深搜时，可能深搜到其他树上去，这是不允许的，强连通分量只能存在单棵树中(由开篇第一句话可知))，我们当然不这么做，我们可以巧妙的选择第二深搜选择的树的顺序，使其不可能深搜到其他树上去。想象一下，如果步骤2是从森林里选择树，那么哪个树是不连通(对于GT来说)到其他树上的呢？就是最后遍历出来的树，它的根节点在步骤1的遍历中离开时间最晚，而且可知它也是该树中离开时间最晚的那个节点。这给我们提供了很好的选择，在第一次深搜遍历时，记录时间i离开的顶点j，即numb[i]=j。那么，我们每次只需找到没有找过的顶点中具有最晚离开时间的顶点直接深搜(对于GT来说)就可以了。每次深搜都得到一个强连通分量。
隐藏性质:
分析到这里，我们已经知道怎么求强连通分量了。但是，大家有没有注意到我们在第二次深搜选择树的顺序有一个特点呢？如果在看上述思路的时候，你的脑子在思考，相信你已经知道了！！！它就是：如果我们把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的节点，那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。为什么呢？首先，应该明确搜索后的图一定是有向无环图呢？废话，如果还有环，那么环上的顶点对应的所有原来图上的顶点构成一个强连通分量，而不是构成环上那么多点对应的独自的强连通分量了。然后就是为什么是拓扑序列，我们在改进分析的时候，不是先选的树不会连通到其他树上（对于反图GT来说），也就是后选的树没有连通到先选的树，也即先出现的强连通分量收缩的点只能指向后出现的强连通分量收缩的点。那么拓扑序列不是理所当然的吗？这就是Kosaraju算法的一个隐藏性质。
Kosaraju_Algorithm:
step1：对原图G进行深度优先遍历，记录每个节点的离开时间。
step2：选择具有最晚离开时间的顶点，对反图GT进行遍历，删除能够遍历到的顶点，这些顶点构成一个强连通分量。
step3：如果还有顶点没有删除，继续step2，否则算法结束。
C++
#include
#include
using namespace std;const int MAXN=110;int n;bool flag[MAXN];//访问标志数组int belg[MAXN];//存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量int numb[MAXN];//结束时间标记,其中numb[i]表示离开时间为i的顶点AdjTableadj[MAXN],radj[MAXN];//邻接表,逆邻接表//用于第一次深搜,求得numb[1..n]的值voidVisitOne(intcur,int&sig){flag[cur]=true;for(inti=1;i<=adj[cur][0];++i){if(false==flag[adj[cur][i]]){VisitOne(adj[cur][i],sig);}}numb[++sig]=cur;}//用于第二次深搜,求得belg[1..n]的值voidVisitTwo(intcur,intsig){flag[cur]=true;belg[cur]=sig;for(inti=1;i<=radj[cur][0];++i){if(false==flag[radj[cur][i]]){VisitTwo(radj[cur][i],sig);}}}//Kosaraju算法,返回为强连通分量个数intKosaraju_StronglyConnectedComponent(){inti,sig;//第一次深搜memset(flag+1,0,sizeof(bool)*n);for(sig=0,i=1;i<=n;++i){if(false==flag[i]){VisitOne(i,sig);}}//第二次深搜memset(flag+1,0,sizeof(bool)*n);for(sig=0,i=n;i>0;--i){if(false==flag[numb[i]]){VisitTwo(numb[i],++sig);}}returnsig;}
⑤ 强连通分量(Kosaraju算法)
{ //判断各个强连通分量是否为出度为0的分量 for(int t = 0; t
⑥ 想问一下图上的第5题 Python代码
在这篇文章中将为大家介绍一些重要的图算法,以及Python 的代码实现。 1、连通分量 具有三个连通分量的图 将上图中的连通分量算法近似看作一种硬聚类算法,该算法旨在寻找相关数据的簇类。举一个具体的例子:假设拥有连接世界上任意城市的.
⑦ 采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。
思路是这样的：
1、从图中任选一个节点，以此节点进行深度优先搜索并将访问的节点做好标记，连通分量数加一。
2、在从图中没有访问的节点集中选一个节点重复1的过程直到所有节点都被标记
⑧ 请设计一个算法，求出无向图G的连通分量个数
intConnect(AdjGraph*G){//参数为邻接表int i,count=0;
DFC(G,0);//图的深度遍历，以0顶点开始
for(int i = 0;i<G->n;i++){
if(visited[i] == 0){//图遍历算法的辅助数组，若为0则没遍历到，说明非连通
count++;
DFS(G,i);
}
}
if(count == 0 )//若上面循环遍历完毕count=0则说明改图连通，只有一个连通分量
count = 1;
return count;
}
⑨ 强连通分量的Tarjan算法思路
这个算法思路不难理解，由开篇第一句话可知，任何一个强连通分量，必定是对原图的深度优先搜索树的子树。那么其实，我们只要确定每个强连通分量的子树的根，然后根据这些根从树的最低层开始，一个一个的拿出强连通分量即可。那么剩下的问题就只剩下如何确定强连通分量的根和如何从最低层开始拿出强连通分量了。
那么如何确定强连通分量的根，在这里我们维护两个数组，一个是indx[1..n]，一个是mlik[1..n]，其中indx[i]表示顶点i开始访问时间，mlik[i]为与顶点i邻接的顶点未删除顶点j的mlik[j]和mlik[i]的最小值(mlik[i]初始化为indx[i])。这样，在一次深搜的回溯过程中，如果发现mlik[i]==indx[i]那么，当前顶点就是一个强连通分量的根，为什么呢？因为如果它不是强连通分量的根，那么它一定是属于另一个强连通分量，而且它的根是当前顶点的祖宗，那么存在包含当前顶点的到其祖宗的回路，可知mlik[i]一定被更改为一个比indx[i]更小的值。
至于如何拿出强连通分量，这个其实很简单，如果当前节点为一个强连通分量的根，那么它的强连通分量一定是以该根为根节点的(剩下节点)子树。在深度优先遍历的时候维护一个堆栈，每次访问一个新节点，就压入堆栈。现 在知道如何拿出了强连通分量了吧？是的，因为当前节点是这个强连通分量中最先被压入堆栈的，那么在当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。当然有人会问真的吗？假设一个节点在当前节点压入堆栈以后压入并且还存在，同时它不属于该强连通分量，那么它一定属于另一个强连通分量，但当前节点是它的根的祖宗，那么这个强连通分量应该在此之前已经被拿出。现 在没有疑问了吧，那么算法介绍就完了。
⑩ 请问数据结构中图的强连通分量是什么能具体解释一下吗
有向图的极大强连通子图，称为强连通分量(strongly connected components)。
在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。
(10)连通分量算法扩展阅读：
强连通分量Tarjan算法
任何一个强连通分量，必定是对原图的深度优先搜索树的子树。那么只要确定每个强连通分量的子树的根，然后根据这些根从树的最低层开始，一个一个的拿出强连通分量即可。
维护两个数组，一个是indx[1..n]，一个是mlik[1..n]，其中indx[i]表示顶点i开始访问时间，mlik[i]为与顶点i邻接的顶点未删除顶点j的mlik[j]和mlik[i]的最小值(mlik[i]初始化为indx[i])。这样，在一次深搜的回溯过程中，如果发现mlik[i]==indx[i]那么，当前顶点就是一个强连通分量的根。
因为如果它不是强连通分量的根，那么它一定是属于另一个强连通分量，而且它的根是当前顶点的祖宗，那么存在包含当前顶点的到其祖宗的回路，可知mlik[i]一定被更改为一个比indx[i]更小的值。
至于拿出强连通分量，如果当前节点为一个强连通分量的根，那么它的强连通分量一定是以该根为根节点的(剩下节点)子树。在深度优先遍历的时候维护一个堆栈，每次访问一个新节点，就压入堆栈。
这样，由于当前节点是这个强连通分量中最先被压入堆栈的，那么在当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。
可以用反证法证明这个做法的正确性。假设一个节点在当前节点压入堆栈以后压入并且还存在，同时它不属于该强连通分量，那么它一定属于另一个强连通分量，但当前节点是它的根的祖宗，那么这个强连通分量应该在此之前已经被拿出。