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

求强连通分量的Kosaraju算法和Tarjan算法的比较一、定义在有向图中，如果两个顶点vi,vj间有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图的每两个顶点都强连通，则称该有向图是一个强连通图。非强连通的有向图的极大强连通子图，称为强连通分量(strongly connected components)。而对于一个无向图，讨论强连通没有意义，因为在无向图中连通就相当于强连通。由一个强连通分量内的所有点所组成的集合称为缩点。在有向图中的所有缩点和所有缩点之间的边所组成的集合称为该有向图的缩图。例子：原图：1243765缩图：1432上面的缩图中的缩点1包含：1、2,； 缩点2包含：3；缩点3包含：4； 缩点4包含：5、6、7。二、求强连通分量的作用把有向图中具有相同性质的点找出来，形成一个集合（缩点），建立缩图，能够方便地进行其它操作，而且时间效率会大大地提高，原先对多个点的操作可以简化为对它们所属的缩点的操作。求强连通分量常常用于求拓扑排序之前，因为原图往往有环，无法进行拓扑排序，而求强连通分量后所建立的缩图则是有向无环图，方便进行拓扑排序。三、Kosaraju算法时间复杂度：O（M+N） 注：M代表边数，N代表顶点数。所需的数据结构：原图、反向图（若在原图中存在vi到vj的有向边，在反向图中就变成为vj到vi的有向边）、标记数组（标记是否遍历过）、一个栈（或记录顶点离开时间的数组）。算法描叙：步骤1：对原图进行深度优先遍历，记录每个顶点的离开时间。 步骤2：选择具有最晚离开时间的顶点，对反向图进行深度优先遍历，并标记能够遍历到的顶点，这些顶点构成一个强连通分量。 步骤3：如果还有顶点没有遍历过，则继续进行步骤2，否则算法结束。hdu1269（Kosaraju算法）代码：#include#includeconst int M=10005;struct nodeint vex;node *next;node *edge1M,*edge2M;bool mark1M,mark2M;int TM,Tcnt,Bcnt;void DFS1(int x)mark1x=true;node *i;for(i=edge1x;i!=NULL;i=i-next)if(!mark1i-vex)DFS1(i-vex);TTcnt=x;Tcnt+;void DFS2(int x)mark2x=true;node *i;for(i=edge2x;i!=NULL;i=i-next)if(!mark2i-vex)DFS2(i-vex);int main()int n,m;while(scanf(%d%d,&n,&m)if(n=0&m=0)break;int i,a,b;for(i=1;ivex=b;t-next=edge1a;edge1a=t;t=(node *)malloc(sizeof(node);t-vex=a;t-next=edge2b;edge2b=t;Tcnt=0;for(i=1;i=0;i-)if(!mark2Ti)DFS2(Ti);Bcnt+;if(Bcnt=1)/如果强连通分量的个数为1则说明该图是强连通图printf(Yesn);elseprintf(Non);return 0;四、Tarjan算法时间复杂度：O（M+N） 注：M代表边数，N代表顶点数。所需的数据结构：原图、标记数组（与Kosaraju算法的标记不同，这里的标记数组是标记顶点是否在栈内）、一个栈、dfn数组（记录顶点被遍历的时间）、low数组（记录顶点或顶点的子树能够追溯到的最早的栈中顶点的遍历时间）。算法描叙：步骤1: 找一个没有被遍历过的顶点v，进行步骤2（v）（遍历时间由1开始累加，若是非连通图，则须重复进行步骤1）。否则，算法结束。 步骤2（v）: 初始化dfnv和lowv的值为当前的遍历时间，并且v进栈；对于v所有的邻接顶点u： （1） 如果u没有被遍历过，则进行步骤2（u），同时维护lowv。（2） 如果u已经被遍历过，但还在栈中（即还不属于任一强连通分量），则维护lowv，否则不做任何操作。 如果有dfnv=lowv，则把栈中的顶点弹出（直到把v都弹出为止），这些顶点组成一个强连通分量。hdu1269（Tarjan算法）代码：#include#include#includeconst int MAX=10005;struct nodeint vex;node *next;node *gMAX;bool insMAX;int dfnMAX,lowMAX,sMAX,sn,belongMAX,outMAX;int cnt,time;void dfs(int i)time+;dfni=lowi=time;ssn=i;sn+;insi=true;int j;node *t;for(t=gi;t!=NULL;t=t-next)j=t-vex;if(dfnj=0)/处理树枝边dfs(j);if(lowjlowi)lowi=lowj;else if(insj&dfnjlowi)/处理后向边lowi=dfnj;if(dfni=lowi)cnt+;doj=ssn-1;sn-;insj=false;while(j!=i);void tarjan(int n)int i;for(i=1;ivex=b;t-next=ga;ga=t;cnt=0;/cnt用于记录强连通分量的个数time=0;sn=0;memset(ins+1,false,n*sizeof(bool);memset(dfn+1,0,n*sizeof(int);tarjan(n);if(cnt=1)/如果强连通分量的个数为1则说明该图是强连通图printf(Yesn);elseprintf(Non);return 0;五、Kosaraju算法和Tarjan算法比较举例子比较两个算法：Kosaraju算法：原图：1243765建立反向图：1243765对原图进行深度优先遍历后，顶点的离开时间分别为：1离开时间为7，2离开时间为5，3离开时间为4，4离开时间为6，5离开时间为3，6离开时间为2，7离开时间为1。则按顶点按离开时间从大到小排列的序列为：1、4、2、3、5、6、7，按上述序列对反向图进行深度优先遍历，属于同一次深度优先遍历的顶点则属于同一个强连通分量（即缩点），结果：1、2属于同一个强连通分量，3自己为一个强连通分量，4自己为一个一个强连通分量，5、6、7属于同一个强连通分量。Tarjan算法：原图：1243765对原图进行深度优先遍历（无须回溯）：下面分析整个dfs过程中的ins数组、dfn数组和low数组的变化情况（遍历前先清0）：遍历顶点1： 数组顶点 ins dfn low1true112false003false004false005false006false007false00遍历顶点2： 数组顶点 ins dfn low1true112true223false004false005false006false007false00遍历顶点3： 数组顶点 ins dfn low1true112true223true334false005false006false007false00遍历顶点5： 数组顶点 ins dfn low1true112true223true334false005true446false007false00遍历顶点6： 数组顶点 ins dfn low1true112true223true334false005true446true557false00遍历顶点7： 数组顶点 ins dfn low1true112true223true334false005true446true557true66离开顶点7： 数组顶点 ins dfn low1true112true223true334false005true446true557true64离开顶点6： 数组顶点 ins dfn low1true112true223true334false005true446true547true64离开顶点5时有dfn5=low5，所以5、6、7组成一个强连通分量： 数组顶点 ins dfn low1true112true223true334false005false446false547false64离开顶点3时有dfn3=low3，所以3自己为一个强连通分量： 数组顶点 ins dfn low1true112true223false334false005false446false547false64离开顶点2： 数组顶点 ins dfn low1true112true213false334false005false446false547false64返回顶点1再遍历顶点4： 数组顶点 ins dfn low1true112true213false334true775false446false547false64离开顶点4时有dfn4=low4，所以4自己为一个强连通分量： 数组顶点 ins dfn low1true112true213false334false775false446false547false64离开顶点1时有dfn1=low1，所以1、2组成一个强连通分量： 数组顶点 ins dfn low1false112false213false334false775false446false547false64结果：1、2属于同一个强连通分量，3自己为一个强连通分量，4自己为一个一个强连通分量，5、6、7属于同一个强连通分量。两个算法的执行步骤不同，但得出的结果都是一致正确的。时间复杂度比较：两个算法的时间复杂度都是O（M+N）（M代表边数，N代表顶点数），但是Kosaraju算法须要进行两次dfs，并且要建立反向图，而Tarjan算法只须就进行一次dfs，在实际的应用中Tarjan算法的时间效率的确比Kosaraju算法要高（网上资料统计出Tarjan算法的时间效率要比Kosaraju算法要高30%左右）。空间复杂度比较： Tarjan算法虽然比Kosaraju算法多用两个一维数组，但虽然Kosaraju算法比Tarjan算法多浪费建立一个反向图的空间，所以总体来说在空间复杂度上还是Tarjan算法比Kosaraju算法要占优势。理解难易程度比较： Kosaraju算法单纯的两次深搜的做法显然比Tarjan算法要容易理解。代码量比较： 两个算法的代码