有向图强连通分量的Tarjan算法分析

1有向图强连通分量的Tarjan算法[有向图强连通分量]在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(stronglyconnected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(stronglyconnectedcomponents)。下图中，子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。直接根据定义，用双向遍历取交集的方法求强连通分量，时间复杂度为O(N^2+M)。更好的方法是Kosaraju算法或Tarjan算法，两者的时间复杂度都是O(N+M)。本文介绍的是Tarjan算法。[Tarjan算法]Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出，Low(u)=Min{DFN(u),Low(v),(u,v)为树枝边，u为v的父节点DFN(v),(u,v)为指向栈中节点的后向边(非横叉边)}当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。算法伪代码如下tarjan(u){DFN[u]=Low[u]=++Index//为节点u设定次序编号和Low初值Stack.push(u)//将节点u压入栈中foreach(u,v)inE//枚举每一条边if(visnotvisted)//如果节点v未被访问过tarjan(v)//继续向下找Low[u]=min(Low[u],Low[v])elseif(vinS)//如果节点v还在栈内Low[u]=min(Low[u],DFN[v])if(DFN[u]==Low[u])//如果节点u是强连通分量的根repeatv=S.pop//将v退栈，为该强连通分量中一个顶点printv2until(u==v)}接下来是对算法流程的演示。从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，DFN[6]=LOW[6]，找到了一个强连通分量。退栈到u=v为止，{6}为一个强连通分量。返回节点5，发现DFN[5]=LOW[5]，退栈后{5}为一个强连通分量。返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4向节点1有后向边，节点1还在栈中，所以LOW[4]=1。节点6已经出栈，(4,6)是横叉边，返回3，(3,4)为树枝边，所以LOW[3]=LOW[4]=1。3继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW[2]=DFN[4]=5。返回1后，发现DFN[1]=LOW[1]，把栈中节点全部取出，组成一个连通分量{1,3,4,2}。至此，算法结束。经过该算法，求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。可以发现，运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(N+M)。求有向图的强连通分量还有一个强有力的算法，为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是O(N+M)。与Trajan算法相比，Kosaraju算法可能会稍微更直观一些。但是Tarjan只用对原图进行一次DFS，不用建立逆图，更简洁。在实际的测试中，Tarjan算法的运行效率也比Kosaraju算法高30%左右。此外，该Tarjan算法与求无向图的双连通分量(割点、桥)的Tarjan算法也有着很深的联系。学习该Tarjan算法，也有助于深入理解求双连通分量的Tarjan算法，两者可以类比、组合理解。求有向图的强连通分量的Tarjan算法是以其发明者RobertTarjan命名的。RobertTarjan还发明了求双连通分量的Tarjan算法，以及求最近公共祖先的离线Tarjan算法，在此对Tarjan表示崇高的敬意。附：tarjan算法的C++程序4voidtarjan(inti){intj;DFN[i]=LOW[i]=++Dindex;instack[i]=true;Stap[++Stop]=i;for(edge*e=V[i];e;e=e-next){j=e-t;if(!DFN[j]){tarjan(j);if(LOW[j]LOW[i])LOW[i]=LOW[j];}elseif(instack[j]&&DFN[j]LOW[i])LOW[i]=DFN[j];}if(DFN[i]==LOW[i]){Bcnt++;do{j=Stap[Stop--];instack[j]=false;Belong[j]=Bcnt;}while(j!=i);}}voidsolve(){inti;Stop=Bcnt=Dindex=0;memset(DFN,0,sizeof(DFN));for(i=1;i=N;i++)if(!DFN[i])tarjan(i);}例1、://poj.org/problem?id=1236分析：题目大意：N(2N100)各学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输，问题1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。2，至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。5也就是：给定一个有向图，求：1)至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点2)至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点顶点数=100解题思路：1.求出所有强连通分量2.每个强连通分量缩成一点，则形成一个有向无环图DAG。3.DAG上面有多少个入度为0的顶点，问题1的答案就是多少在DAG上要加几条边，才能使得DAG变成强连通的，问题2的答案就是多少加边的方法：要为每个入度为0的点添加入边，为每个出度为0的点添加出边假定有n个入度为0的点，m个出度为0的点，如何加边？把所有入度为0的点编号0,1,2,3,4....N-1每次为一个编号为i的入度0点可达的出度0点，添加一条出边，连到编号为(i+1)%N的那个出度0点,这需要加n条边若m=n，则加了这n条边后，已经没有入度0点，则问题解决，一共加了n条边若mn，则还有m-n个入度0点，则从这些点以外任取一点，和这些点都连上边，即可，这还需加m-n条边。所以，max(m,n)就是第二个问题的解此外：当只有一个强连通分支的时候，就是缩点后只有一个点，虽然入度出度为0的都有一个，但是实际上不需要增加清单的项了，所以答案是1，0；一句话：强连通分量缩点求入度为0的个数和出度为0的分量个数提示：缩点，并不是真的新建一个图，只是对同一个强连通分量涂一种颜色即可。参考程序：#includecstdlib#includeiostream#includevector#includestack#includecstringusingnamespacestd;constintmaxn=10000;intpre[maxn],lowlink[maxn],sccno[maxn],dfsclock,scccnt;vectorintG[maxn];stackintS;intn;voidtarjan(intu){pre[u]=lowlink[u]=++dfsclock;S.push(u);for(inti=0;iG[u].size();i++)6{intv=G[u][i];if(!pre[v]){dfs(v);lowlink[u]=min(lowlink[u],lowlink[v]);}elseif(!sccno[v])lowlink[u]=min(lowlink[u],pre[v]);}if(lowlink[u]==pre[u]){scccnt++;for(;;){intx=S.top();S.pop();sccno[x]=scccnt;if(x==u)break;}}}voidfind(intn){dfsclock=scccnt=0;memset(sccno,0,sizeof(sccno));memset(pre,0,sizeof(pre));for(inti=0;in;i++){if(!pre[i])tarjan(i);}}intmain(){intn;cinn;for(inti=0;in;i++){inta;while(cina&&a!=0){G[i].push_back(a-1);}}find(n);intin0[maxn],out0[maxn];for(inti=1;i=scccnt;i++)in0[i]=out0[i]=1;for(intu=0;un;u++)for(intu=0;un;u++)7for(inti=0;iG[u].size();i++){intv=G[u][i];if(sccno[u]!=sccno[v])in0[sccno[v]]=out0[sccno[u]]=0;}inta=0,b=0;intans1,ans2;for(inti=1;i=scccnt;i++){if(in0[i])a++;if(out0[i])b++;}ans2=max(a,b);if(scccnt==1){a=1,ans2=0;}coutaendl;coutans2endl;return0;}例2、://codevs.cn/problem/2822/该题数据范围：n=1000,m=10000解题报告：首先直接跑一下tarjan。。。。。。。。。。。强连通分量（注：不包括单独一个点）的数量就是第一问的答案。。。。。。。。。。。。。接下来回答第二问。。。。。。。。。。。。。可以进行暴力缩点（新建图，并记录出度）。。然后你就会神奇的发现一个很神奇的地方。。。出度为0的点所在的强连通分量（且只有一个联通分量）就是答案。。。这时你输出这个强连通分量即可。。。。。。。注意，若该强连通分量是一个点，就输出-1。。参考程序：#includecstdio#includecstring#includealgorithm#includeiostreamusingnamespacestd;constintMAX_N=1005,MAX_M=10005;structnode{intv,next;}E[MAX_M];inthead[MAX_N],top=0;inlinevoidadd(intu,intv)8{E[++top].v=v;E[top].next=head[u];head[u]=top;}intn,m;voidinit(){scanf(%d%d,&n,&m);for(inti=1;i=m;i++){intu,v;scanf(%d%d,&u,&v);add(u,v);}}intdfn[MAX_N],low[MAX_N],sta[MAX_N],Tm=0,scc=0,ou[MAX_N],sz=0;intcol[MAX_N],num[MAX_N];boolvis[MAX_N],inq[MAX_N];voidtarjan(intx){sta[++sz]=x;inq[x]=vis[x]=1;low[x]=dfn[x]=++Tm;for(inti=head[x];i;i=E[i].next)if(!vis[E[i].v]){tarjan(E[i].v);low[x]=min(low[x],low[E[i].v]);}elseif(inq[E[i].v])low[x]=min(low[