求强连通分量的Kosaraju算法和Tarjan算法的比较 by ljq.doc

《求强连通分量的Kosaraju算法和Tarjan算法的比较 by ljq.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求强连通分量的Kosaraju算法和Tarjan算法的比较一、定义在有向图中，如果两个顶点vi,vj间有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(stronglyconnected)。如果有向图的每两个顶点都强连通，则称该有向图是一个强连通图。非强连通的有向图的极大强连通子图，称为强连通分量(stronglyconnectedcomponents)。而对于一个无向图，讨论强连通没有意义，因为在无向图中连通就相当于强连通。由一个强连通分量内的所有点所组成的集合称为缩点。在有向图中的所有缩点和所有缩点之间的边所组成的集合称为该

2、有向图的缩图。例子：原图：1243765缩图：1432上面的缩图中的缩点1包含：1、2,；缩点2包含：3；缩点3包含：4；缩点4包含：5、6、7。二、求强连通分量的作用把有向图中具有相同性质的点找出来，形成一个集合（缩点），建立缩图，能够方便地进行其它操作，而且时间效率会大大地提高，原先对多个点的操作可以简化为对它们所属的缩点的操作。求强连通分量常常用于求拓扑排序之前，因为原图往往有环，无法进行拓扑排序，而求强连通分量后所建立的缩图则是有向无环图，方便进行拓扑排序。三、Kosaraju算法时间复杂度：O（M+N）注：M代表边数，N代表顶点数。所需的数据结构：原图、

3、反向图（若在原图中存在vi到vj的有向边，在反向图中就变成为vj到vi的有向边）、标记数组（标记是否遍历过）、一个栈（或记录顶点离开时间的数组）。算法描叙：　　步骤1：对原图进行深度优先遍历，记录每个顶点的离开时间。　　步骤2：选择具有最晚离开时间的顶点，对反向图进行深度优先遍历，并标记能够遍历到的顶点，这些顶点构成一个强连通分量。步骤3：如果还有顶点没有遍历过，则继续进行步骤2，否则算法结束。hdu1269（Kosaraju算法）代码：#include#includeconstintM=10005;structnode{intv

4、ex;node*next;};node*edge1[M],*edge2[M];boolmark1[M],mark2[M];intT[M],Tcnt,Bcnt;voidDFS1(intx){mark1[x]=true;node*i;for(i=edge1[x];i!=NULL;i=i->next){if(!mark1[i->vex]){DFS1(i->vex);}}T[Tcnt]=x;Tcnt++;}voidDFS2(intx){mark2[x]=true;node*i;for(i=edge2[x];i!=NULL;i=i->next){if(!mark2[i->v

5、ex]){DFS2(i->vex);}}}intmain(){intn,m;while(scanf("%d%d",&n,&m)){if(n==0&&m==0){break;}inti,a,b;for(i=1;i<=n;i++){mark1[i]=mark2[i]=false;edge1[i]=NULL;edge2[i]=NULL;}node*t;while(m--){scanf("%d%d",&a,&b);t=(node*)malloc(sizeof(node));t->vex=b;t->next=edge1[a];edge1[a]=t;t=(node*)mall

6、oc(sizeof(node));t->vex=a;t->next=edge2[b];edge2[b]=t;}Tcnt=0;for(i=1;i<=n;i++){if(!mark1[i]){DFS1(i);}}Bcnt=0;//Bcnt用于记录强连通分量的个数for(i=Tcnt-1;i>=0;i--){if(!mark2[T[i]]){DFS2(T[i]);Bcnt++;}}if(Bcnt==1)//如果强连通分量的个数为1则说明该图是强连通图{printf("Yes");}else{printf("No");}}return0;}四、Tarjan算法时间

7、复杂度：O（M+N）注：M代表边数，N代表顶点数。所需的数据结构：原图、标记数组（与Kosaraju算法的标记不同，这里的标记数组是标记顶点是否在栈内）、一个栈、dfn数组（记录顶点被遍历的时间）、low数组（记录顶点或顶点的子树能够追溯到的最早的栈中顶点的遍历时间）。算法描叙：　　步骤1:找一个没有被遍历过的顶点v，进行步骤2（v）（遍历时间由1开始累加，若是非连通图，则须重复进行步骤1）。否则，算法结束。　　步骤2（v）:初始化dfn[v]和low[v]的值为当前的遍历时间，并且v进栈；　　对于v所有的邻接顶点u：（1）如果u没有被遍历过，则进行步骤2（u），

8、同时维护l