轉自：http://www.byvoid.com/blog/scc-tarjan/

http://blog.csdn.net/geniusluzh/article/details/6601514

在有向圖G中，如果兩個頂點間至少存在一條路徑，稱兩個頂點強連通(strongly connected)。如果有向圖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為根的搜索子樹上所有節點是一個強連通分量。

接下來是對算法流程的演示。

從節點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。

繼續回到節點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算法是以其發明者Robert Tarjan命名的。Robert Tarjan還發明了求雙連通分量的Tarjan算法，以及求最近公共祖先的離線Tarjan算法，在此對Tarjan表示崇高的敬意。

附：tarjan算法的C++程序

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); }

強連通分量是有向圖中的概念，我們先說強連通分量的定義吧：在一個圖的子圖中，任意兩個點相互可達，也就是存在互通的路徑，那么這個子圖就是強連通分量（或者稱為強連通分支）。如果一個有向圖的任意兩個點相互可達，那么這個圖就稱為強連通圖。

? ? ? ? 我們常用的求強連通分量的算法有兩個，一個是Kosaraju算法，這個算法是基于兩次dfs來實現的；還有一個就是Tarjan算法，這個算法完成一次dfs就可以找到圖中的強連通分支。我的這篇文章主要介紹Tarjan算法。

? ? ? ?Tarjan算法是基于這樣一個原理：如果u是某個強連通分量的根，那么：

（1）u不存在路徑可以返回到它的祖先

（2）u的子樹也不存在路徑可以返回到u的祖先。

? ? ? ? 因此我們在實現Tarjan算法的時候，使用dfsnum[i]記錄節點i被訪問的時間，也可以理解為在訪問該點之前已經訪問的點的個數。然后使用數組low[i]記錄點i或者i的子樹最小可以返回到的節點（在棧中）的次序號。

? ? ? ? 這里還要說一下low[i]的更新過程，

if(v是i向下dfs的樹邊) low[i]=min(low[i],low[v]);//這里也就是說low[i]表示i或者i的子樹所能追回到的最小的點序號。

if(v不是樹邊也不是橫叉邊) low[i]=min(low[i],dfsnum[v]);//其實這里你直接更新成low[v]代替dfsnum[v]也是可以的

? ? ? ? 根據上面的原理，我們可以發現只有當dfsnum[i]==low[i]的時候就正好是強連通分量的根。這個時候我們把在棧中的點（在遇到根之前在棧中的點）出棧，并且標記好點所屬的強連通分支的編號。(dfsnum[i]==low[i]主要思想還是說明了，有從i經過一些結點回到i結點的回路，有環肯定就是強聯通分支)

? ? ? ? 整個Tarjan算法跑下來就可以完成強連通分支的求解了。

? ? ? ? 下面我貼上我的在HDU 1269上判斷一個圖是否是強連通圖的代碼，這個代碼其實就完成了Tarjan算法，最后只要簡單判斷下整個圖是否是只有一個強連通分支就可以了。

#include <string.h> #include <stdio.h> #include <stdlib.h> #define MAX 100010 int dfsnum[MAX],dfsNum,low[MAX]; int sccnum[MAX],sccNum; int instack[MAX],st[MAX],top;typedef struct EDGE {int v,next; }edge; edge e[MAX]; int edgeNum; int head[MAX];void insertEdge(int a,int b)//邊a--->b {e[edgeNum].v=b;//v記錄的是邊的尾e[edgeNum].next=head[a];//以點a開始的所有鄰接邊head[a]=edgeNum++;//以點a為頭的第一條邊；同理，第二條邊是e[head[a]].next, }void Tarjan(int i) {dfsnum[i]=low[i]=++dfsNum;st[top++]=i;instack[i]=1;int j=head[i];for(j=head[i];j!=-1;j=e[j].next){int v=e[j].v;if(dfsnum[v]==0)//為樹邊{Tarjan(v);if(low[i]>low[v])low[i]=low[v];}else if(instack[v]){if(low[i]>dfsnum[v])low[i]=dfsnum[v];}}if(dfsnum[i]==low[i]){do{top--;sccnum[st[top]]=sccNum;//標記在第sccNum強連通分支中的點的標記為sccNuminstack[st[top]]=0;}while(top>=0&&st[top]!=i);sccNum++;} } void solve(int n) {int i;memset(dfsnum,0,sizeof(dfsnum));memset(instack,0,sizeof(instack));dfsNum=0;top=0;sccNum=0;for(i=1;i<=n;i++){if(dfsnum[i]==0)Tarjan(i);} } int main() {int n,m;int a,b,i;while(scanf("%d %d",&n,&m)){if(m==0&&n==0)break;memset(head,-1,sizeof(head));edgeNum=0;for(i=0;i<m;i++){scanf("%d %d",&a,&b);insertEdge(a,b);}solve(n);if(sccNum==1)printf("Yes\n");elseprintf("No\n");}return 0; }

總結

以上是生活随笔為你收集整理的有向图强连通分量tarjan算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。