基本介紹
- 中文名：強連通分量
- 外文名：strongly connected components
- 別名：強連通分支
算法思路,算法總結,
算法思路
Kosaraju算法思路
這個算法可以說是最容易理解，最通用的算法，其比較關鍵的部分是同時套用了原圖G和反圖GT。步驟1：先用對原圖G進行深搜形成森林(樹)，步驟2：然後任選一棵樹對其進行深搜(注意這次深搜節點A能往子節點B走的要求是EAB存在於反圖GT)，能遍歷到的頂點就是一個強連通分量。餘下部分和原來的森林一起組成一個新的森林，繼續步驟2直到 沒有頂點為止。
改進思路：
當然，基本思路實現起來是比較麻煩的(因為步驟2每次對一棵樹進行深搜時，可能深搜到其他樹上去，這是不允許的，強連通分量只能存在單棵樹中(由開篇第一句話可知))，我們當然不這么做，我們可以巧妙的選擇第二深搜選擇的樹的順序，使其不可能深搜到其他樹上去。想像一下，如果步驟2是從森林裡選擇樹，那么哪個樹是不連通(對於GT來說)到其他樹上的呢？就是最後遍歷出來的樹，它的根節點在步驟1的遍歷中離開時間最晚，而且可知它也是該樹中離開時間最晚的那個節點。這給我們提供了很好的選擇，在第一次深搜遍歷時，記錄時間i離開的頂點j，即numb[i]=j。那么，我們每次只需找到沒有找過的頂點中具有最晚離開時間的頂點直接深搜(對於GT來說)就可以了。每次深搜都得到一個強連通分量。
隱藏性質:
分析到這裡，我們已經知道怎么求強連通分量了。但是，大家有沒有注意到我們在第二次深搜選擇樹的順序有一個特點呢？如果在看上述思路的時候，你的腦子在思考，相信你已經知道了！！！它就是：如果我們把求出來的每個強連通分量收縮成一個點，並且用求出每個強連通分量的順序來標記收縮後的節點，那么這個順序其實就是強連通分量收縮成點後形成的有向無環圖的拓撲序列。為什麼呢？首先，應該明確搜尋後的圖一定是有向無環圖呢？廢話，如果還有環，那么環上的頂點對應的所有原來圖上的頂點構成一個強連通分量，而不是構成環上那么多點對應的獨自的強連通分量了。然後就是為什麼是拓撲序列，我們在改進分析的時候，不是先選的樹不會連通到其他樹上（對於反圖GT來說），也就是後選的樹沒有連通到先選的樹，也即先出現的強連通分量收縮的點只能指向後出現的強連通分量收縮的點。那么拓撲序列不是理所當然的嗎？這就是Kosaraju算法的一個隱藏性質。
偽代碼
Kosaraju_Algorithm:
step1：對原圖G進行深度優先遍歷，記錄每個節點的離開時間。
step2：選擇具有最晚離開時間的頂點，對反圖GT進行遍歷，刪除能夠遍歷到的頂點，這些頂點構成一個強連通分量。
step3：如果還有頂點沒有刪除，繼續step2，否則算法結束。
實現代碼
C++
#include<iostream>#include<cstring>using namespace std;const int MAXN=110;int n;bool flag[MAXN];//訪問標誌數組int belg[MAXN];//存儲強連通分量,其中belg[i]表示頂點i屬於第belg[i]個強連通分量int numb[MAXN];//結束時間標記,其中numb[i]表示離開時間為i的頂點AdjTableadj[MAXN],radj[MAXN];//鄰接表,逆鄰接表//用於第一次深搜,求得numb[1..n]的值voidVisitOne(int cur,int &sig){ flag[cur]=true; for(int i=1;i<=adj[cur][0];++i) if(false==flag[adj[cur][i]]) VisitOne(adj[cur][i],sig); numb[++sig]=cur;}//用於第二次深搜,求得belg[1..n]的值voidVisitTwo(int cur,intsig){ flag[cur]=true; belg[cur]=sig; for(int i=1;i<=radj[cur][0];++i) if(false==flag[radj[cur][i]]) VisitTwo(radj[cur][i],sig);}//Kosaraju算法,返回為強連通分量個數int Kosaraju_StronglyConnectedComponent(){ int i,sig; //第一次深搜 memset(flag+1,0,sizeof(bool)*n); for(sig=0,i=1;i<=n;++i) if(false==flag[i]) VisitOne(i,sig); //第二次深搜 memset(flag+1,0,sizeof(bool)*n); for(sig=0,i=n;i>0;--i) if(false==flag[numb[i]]) VisitTwo(numb[i],++sig); return sig;}Tarjan算法思路
這個算法思路不難理解，由開篇第一句話可知，任何一個強連通分量，必定是對原圖的深度優先搜尋樹的子樹。那么其實，我們只要確定每個強連通分量的子樹的根，然後根據這些根從樹的最低層開始，一個一個的拿出強連通分量即可。那么剩下的問題就只剩下如何確定強連通分量的根和如何從最低層開始拿出強連通分量了。
那么如何確定強連通分量的根，在這裡我們維護兩個數組，一個是indx[1..n]，一個是mlik[1..n]，其中indx[i]表示頂點i開始訪問時間，mlik[i]為與頂點i鄰接的頂點未刪除頂點j的mlik[j]和mlik[i]的最小值(mlik[i]初始化為indx[i])。這樣，在一次深搜的回溯過程中，如果發現mlik[i]==indx[i]那么，當前頂點就是一個強連通分量的根，為什麼呢？因為如果它不是強連通分量的根，那么它一定是屬於另一個強連通分量，而且它的根是當前頂點的祖宗，那么存在包含當前頂點的到其祖宗的迴路，可知mlik[i]一定被更改為一個比indx[i]更小的值。
至於如何拿出強連通分量，如果當前節點為一個強連通分量的根，那么它的強連通分量一定是以該根為根節點的(剩下節點)子樹。在深度優先遍歷的時候維護一個堆疊，每次訪問一個新節點，就壓入堆疊。這樣，由於當前節點是這個強連通分量中最先被壓入堆疊的，那么在當前節點以後壓入堆疊的並且仍在堆疊中的節點都屬於這個強連通分量。可以用反證法證明這個做法的正確性。假設一個節點在當前節點壓入堆疊以後壓入並且還存在，同時它不屬於該強連通分量，那么它一定屬於另一個強連通分量，但當前節點是它的根的祖宗，那么這個強連通分量應該在此之前已經被拿出。
實現代碼（pascal）
由於不同人編輯而註明，代碼中數組dfn為上述indx，low為mlik
type inf=recordx,next:longint;end;var dfn,low,stk,hash,nar:array[1..10000] of longint;//stk為棧，nar[i]記錄i所對應的強連通分量編號e:array[1..50000] of inf;//鄰接鍊表存圖flag,vis:array[1..10000] of boolean;//flag記錄是否在棧中，vis記錄是否遍歷過n,m,i,u,v,top,cnt,ant:longint;//cnt是記錄時間的指針，ant是記錄強連通分量編號的指針procedure dfs(i:longint);//Tarjan求強連通分量var u:longint;begin inc(cnt);//記錄時間 dfn[i]:=cnt; low[i]:=cnt;//更新dfn與low vis[i]:=true;//表示i已經被遍歷過 inc(top); stk[top]:=i; flag[i]:=true;//表示i在棧中 u:=hash[i]; while u<>0 do begin if not vis[e[u].x] then begin dfs(e[u].x);//先遍歷子樹後更新low low[i]:=min(low[i],low[e[u].x]); end else if flag[e[u].x] then low[i]:=min(low[i],low[e[u].x]); u:=e[u].next; end; if low[i]=dfn[i] then//表明i為一個強連通分量的根節點 begin inc(ant); while stk[top]<>i do//彈棧記錄強連通分量 begin nar[stk[top]]:=ant; flag[stk[top]]:=false; stk[top]:=0; dec(top); end; nar[stk[top]]:=ant; flag[stk[top]]:=false; stk[top]:=0; dec(top); end;end;
實現代碼（C++）
int low[N],dfn[N];bool instack[N];stack<int>st;struct LIST{ int v; LIST *next;};LIST *head[N]={NULL};void tarjan(int v){ dfn[v]=low[v]=time++; st.push(v); instack[v]=true; for(LIST *p=head[v];p!=NULL;p=p->next) { if(!dfn[p->v]) { tarjan(p->v); low[v]=min(low[v],low[p->v]); } else if(instack[p->v]) low[v]=min(low[v],dfn[p->v]); } if(dfn[v]==low[v]) { cout<<"{ "; do { v=st.top(); st.pop(); instack[v]=false; cout<<v<<' '; }while(dfn[v]!=low[v]); cout<<"}"<<endl; }}Gabow算法思路
這個算法其實就是Tarjan算法的變異體，我們觀察一下，只是它用第二個堆疊來輔助求出強連通分量的根，而不是Tarjan算法裡面的indx[]和mlik[]數組。那么，我們說一下如何使用第二個堆疊來輔助求出強連通分量的根。
我們使用類比方法，在Tarjan算法中，每次mlik[i]的修改都是由於環的出現(不然，mlik[i]的值不可能變小)，每次出現環，在這個環裡面只剩下一個mlik[i]沒有被改變(深度最低的那個)，或者全部被改變，因為那個深度最低的節點在另一個環內。那么Gabow算法中的第二堆疊變化就是刪除構成環的節點，只剩深度最低的節點，或者全部刪除，這個過程是通過出棧來實現，因為深度最低的那個頂點一定比前面的先訪問，那么只要出棧一直到棧頂那個頂點的訪問時間不大於深度最低的那個頂點。其中每個被彈出的節點屬於同一個強連通分量。那有人會問：為什麼彈出的都是同一個強連通分量？因為在這個節點訪問之前，能夠構成強連通分量的那些節點已經被彈出了，這個對Tarjan算法有了解的都應該清楚，那么Tarjan算法中的判斷根我們用什麼來代替呢？想想，其實就是看看第二個堆疊的頂元素是不是當前頂點就可以了。
現 在，你應該明白其實Tarjan算法和Gabow算法其實是同一個思想的不同實現，但是，Gabow算法更精妙，時間更少(不用頻繁更新mlik[])。
偽代碼
Gabow_Algorithm:
步驟1:
找一個沒有被訪問過的節點v，goto step2(v)。否則，算法結束。
步驟2(v):
將v壓入堆疊stk1[]和stk2[]
對於v所有的鄰接頂點u：
1) 如果沒有訪問過，則step2(u)
2) 如果訪問過，但沒有刪除，維護stk2[](處理環的過程)
如果stk2[]的頂元素==v，那么輸出相應的強連通分量
實現代碼
C++：#include<iostream>using namespace std;const intMAXN=110;typedef int AdjTable[MAXN];//鄰接表類型int n;int int m[MAXN];//標記進入頂點時間int belg[MAXN];//存儲強連通分量,其中belg[i]表示頂點i屬於第belg[i]個強連通分量int stk1[MAXN];//輔助堆疊int stk2[MAXN];//輔助堆疊AdjTablead j[MAXN];//鄰接表//深搜過程,該算法的主體都在這裡void Visit(intcur,int&sig,int&scc_num){ int i; int m[cur] = ++sig; stk1[++stk1[0]] = cur; stk2[++stk2[0]] = cur; for(i=1;i<=adj[cur][0];++i) { if(0==intm[adj[cur][i]]) { Visit(adj[cur][i],sig,scc_num); } else if(0==belg[adj[cur][i]]) { while(intm[stk2[stk2[0]]]>intm[adj[cur][i]]) --stk2[0]; } } if (stk2[stk2[0]]==cur) { --stk2[0];++scc_num; do { belg[stk1[stk1[0]]]=scc_num; }while(stk1[stk1[0]--]!=cur); }}//Gabow算法,求解belg[1..n],且返回強連通分量個數,int Gabow_StronglyConnectedComponent(){ int i,sig,scc_num; memset(belg+1,0,sizeof(int)*n); memset(intm+1,0,sizeof(int)*n); sig=0;scc_num=0;stk1[0]=0;stk2[0]=0; for(i=1;i<=n;++i) { if(0==intm[i]) Visit(i,sig,scc_num); } return scc_num;}Pascalprocedure tarjan(r:longint);var x,i,j:longint;begin inc(timez);time[r]:=timez;low[r]:=timez; inc(top);zh[top]:=r; for i:=p1[r]top2[r] do begin j:=e[i].y; iftime[j]=0thentarjan(j); iflow[j]<low[r]thenlow[r]:=low[j]; end; if time[r]=low[r] then repeat x:=zh[top]; num[x]:=r; low[x]:=n+1;//這句話千萬別忘了 dec(top); until x = r;end;算法總結
做一個總結：Kosaraju算法的第二次深搜隱藏了一個拓撲性質，而Tarjan算法和Gabow算法省略了第二次深搜，所以，它們不具有拓撲性質。Tarjan算法用堆疊和標記，Gabow用兩個堆疊（其中一個堆疊的實質是代替了Tarjan算法的標記部分）來代替Kosaraju算法的第二次深搜，所以只用一次深搜，效率比Kosaraju算法要高。
