Tarjan算法详细讲解

Tarjan算法讲解的博客网上找到三篇比较好的,现在都转载了,个人只研究了第一篇,正如博主所说,讲的标比较详细,清晰,剩下两篇也可以看一下.

卿学姐视频讲解 https://www.bilibili.com/video/av/

以下内容转自:http://www.cnblogs.com/uncle-lu/p/5876729.html

全网最详细tarjan算法讲解，我不敢说别的。反正其他tarjan算法讲解，我看了半天才看懂。我写的这个，读完一遍，发现原来tarjan这么简单！

强连通图： 如果 在一个有向图G中，每两个点都强连通，我们就叫这个图，强连通图。

而在这个有向图中，点1 2 3组成的这个子图，是整个有向图中的强连通分量。

解答树：就是一个可以来表达出递归枚举的方式的树（图），其实也可以说是递归图。。反正都是一个作用，一个展示从“什么都没有做”开始到“所有结求出来”逐步完成的过程。“过程！”

而为了存储整个强连通分量，这里挑选的容器是，堆栈。每次一个新节点出现，就进站，如果这个点有 出度 就继续往下找。直到找到底，每次返回上来都看一看子节点与这个节点的LOW值，谁小就取谁，保证最小的子树根。如果找到DFN［］＝＝LOW［］就说明这个节点是这个强连通分量的根节点（毕竟这个LOW［］值是这个强连通分量里最小的。）最后找到强连通分量的节点后，就将这个栈里，比此节点后进来的节点全部出栈，它们就组成一个全新的强连通分量。

先来一段伪代码压压惊：

tarjan(u){ 
    　　DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值 　　Stack.push(u) // 将节点u压入栈中 　　for each (u, v) in E // 枚举每一条边 　　　　if (v is not visted) // 如果节点v未被访问过 　　　　　　　　tarjan(v) // 继续向下找 　　　　　　　　Low[u] = min(Low[u], Low[v]) 　　　　else if (v in S) // 如果节点u还在栈内 　　　　　　　　Low[u] = min(Low[u], DFN[v]) 　　if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根 　　repeat v = S.pop // 将v退栈，为该强连通分量中一个顶点 　　print v 　　until (u== v) } 

这个时候就完了吗？！

你以为就完了吗？！

然而并没有完，万一你只走了一遍tarjan整个图没有找完怎么办呢？！

所以。tarjan的调用最好在循环里解决。

like 如果这个点没有被访问过，那么就从这个点开始tarjan一遍。

因为这样好让每个点都被访问到。

来一道裸代码。
输入：
一个图有向图。
输出：
它每个强连通分量。

这个图就是刚才讲的那个图。一模一样。

input: 6 8 1 3 1 2 2 4 3 4 3 5 4 6 4 1 5 6 output: 6 5 3 4 2 1 

#include 
     #include 
     #include 
     using namespace std; struct node { 
    int v,next; }edge[1001]; int DFN[1001],LOW[1001]; int stack[1001],heads[1001],visit[1001],cnt,tot,index; void add(int x,int y) { 
    edge[++cnt].next=heads[x]; edge[cnt].v = y; heads[x]=cnt; return ; } void tarjan(int x)//代表第几个点在处理。递归的是点。 { 
    DFN[x]=LOW[x]=++tot;// 新进点的初始化。 stack[++index]=x;//进站 visit[x]=1;//表示在栈里 for(int i=heads[x];i!=-1;i=edge[i].next) { 
    if(!DFN[edge[i].v]) { 
   //如果没访问过 tarjan(edge[i].v);//往下进行延伸，开始递归 LOW[x]=min(LOW[x],LOW[edge[i].v]);//递归出来，比较谁是谁的儿子／父亲，就是树的对应关系，涉及到强连通分量子树最小根的事情。 } else if(visit[edge[i].v ]){ 
    //如果访问过，并且还在栈里。 LOW[x]=min(LOW[x],DFN[edge[i].v]);//比较谁是谁的儿子／父亲。就是链接对应关系 } } if(LOW[x]==DFN[x]) //发现是整个强连通分量子树里的最小根。 { 
    do{ 
    printf("%d ",stack[index]); visit[stack[index]]=0; index--; }while(x!=stack[index+1]);//出栈，并且输出。 printf("\n"); } return ; } int main() { 
    memset(heads,-1,sizeof(heads)); int n,m; scanf("%d%d",&n,&m); int x,y; for(int i=1;i<=m;i++) { 
    scanf("%d%d",&x,&y); add(x,y); } for(int i=1;i<=n;i++) if(!DFN[i]) tarjan(1);//当这个点没有访问过，就从此点开始。防止图没走完 return 0; } 

以下内容转自:http://blog.csdn.net/jeryjeryjery/article/details/

所以我们在回溯的过程中就能够通过判断节点的low值和DFN值是否相等来判断是否已经找到一个子连通图。由于该连通图中 的DFN值和low值相等的节点是该连通图中第一个被访问到的节点，又根据栈的特性，则该节点在最里面。所以能够通过不停 的弹栈，直到弹出该DFN值和low值相同的节点来弹出该连通图中所有的节点。

Tarjan算法的C++实现代码如下，可以配合上面的图加以理解：

#include 
     using namespace std; int DFN[105]; //记录在做dfs时节点的搜索次序 int low[105]; //记录节点能够找到的最先访问的祖先的记号 int count=1; //标记访问次序，时间戳 int stack[105]; //压入栈中 int top=-1; int flag[105]; //标记节点是否已经在栈中 int number=0; int j; int matrix[105][105]={ 
   { 
   0,1,1,0,0,0},{ 
   0,0,0,1,0,0},{ 
   0,0,0,1,1,0},{ 
   1,0,0,0,0,1},{ 
   0,0,0,0,0,1},{ 
   0,0,0,0,0,0}}; int length; //图的长度 void tarjan(int u){ 
    DFN[u]=low[u]=count++; //初始化两个值，自己为能找到的最先访问的祖先 stack[++top]=u; flag[u]=1; //标记为已经在栈中 for(int v=0;v<length;v++){ 
    if(matrix[u][v]){ 
    if(!DFN[v]){ 
    //如果点i没有被访问过 tarjan(v); //递归访问 if(low[v]<low[u]) low[u]=low[v]; //更新能找的到祖先 } else{ 
    //如果访问过了，并且该点的DFN更小，则 if(DFN[v]<low[u]&&flag[v]) //flag[v]这个判断条件很重要，这样可以避免已经确定在其他联通图的v,因为u到v的单向边而影响到u的low low[u]=DFN[v]; //也就是已经确定了的联通图要剔除掉，剔除的办法就是判断其还在栈中，因为已经确定了的连通图的点 } //flag在下面的do while中已经设为0了(即已经从栈中剔除了) } } //往后回溯的时候，如果发现DFN和low相同的节点，就可以把这个节点之后的节点全部弹栈，构成连通图 if(DFN[u]==low[u]){ 
    number++; //记录连通图的数量 do{ 
    j=stack[top--]; //依次取出，直到u cout<<j<<" "; flag[j]=0; //设置为不在栈中 }while(j!=u); cout<<endl; } } int main(){ 
    memset(DFN,0,sizeof(DFN)); //数据的初始化 memset(low,0,sizeof(low)); memset(flag,0,sizeof(flag)); length=6; tarjan(0); cout<<endl; for(int i=0;i<6;i++){ 
    cout<<"DFN["<<i<<"]:"<<DFN[i]<<" low["<<i<<"]:"<<low[i]<<endl; } return 0; } 

以下内用转自:http://blog.csdn.net/wsniyufang/article/details/

[有向图强连通分量]
在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(stronglyconnected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。

下图中，子图{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的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出，

当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。

算法伪代码如下:

tarjan(u) { 
    DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值 Stack.push(u) // 将节点u压入栈中 for each (u, v) in E // 枚举每一条边 if (v is not visted) // 如果节点v未被访问过 tarjan(v) // 继续向下找 Low[u] = min(Low[u], Low[v]) else if (v in S) // 如果节点u还在栈内 Low[u] = min(Low[u], DFN[v]) if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根 repeat v = S.pop // 将v退栈，为该强连通分量中一个顶点 print v until (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已经出栈，不再访问6，返回3，(3,4)为树枝边，所以LOW[3]=LOW[4]=1。

继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW[2]=4。返回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算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法，以及求最近公共祖先的离线Tarjan算法，在此对Tarjan表示崇高的敬意。

代码:

void tarjan(int i) { 
    int j; 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]; } else if (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); } } void solve() { 
    int i; Stop=Bcnt=Dindex=0; memset(DFN,0,sizeof(DFN)); for (i=1; i<=N; i++) if (!DFN[i]) tarjan(i); }