-
強連通分量
鎖定
- 中文名
- 強連通分量
- 外文名
- strongly connected component
- 所屬學科
- 圖論
- 別 名
- 強連通分支
強連通分量定義
如果一個有向圖G，對於其中任意兩個頂點v,u，都存在從v到u以及從u到v的有向路徑，則稱G為強連通圖。而在一個不是強連通圖的有向圖G中，若其中兩個頂點u、v在兩個方向上都存在有向路徑，則稱u和v強連通。
強連通分量算法思路
強連通分量Kosaraju算法
Kosaraju算法可以説是最容易理解，最常用的算法，其比較關鍵的部分是同時應用了原圖G和反圖GT。步驟1：先用對原圖G進行深搜生成樹，步驟2：然後任選一棵樹對其進行深搜(注意這次深搜節點A能往子節點B走的要求是EAB存在於反圖GT)，能遍歷到的頂點就是一個強連通分量。餘下部分和原來的樹一起組成一個新的樹，繼續步驟2直到 沒有頂點為止。
改進思路：
當然，基本思路實現起來是比較麻煩的(因為步驟2每次對一棵樹進行深搜時，可能深搜到其他樹上去，這是不允許的，強連通分量只能存在單棵樹中(由開篇第一句話可知))，我們當然不這麼做，我們可以巧妙的選擇第二深搜選擇的樹的順序，使其不可能深搜到其他樹上去。想象一下，如果步驟2是從森林裏選擇樹，那麼哪個樹是不連通(對於GT來説)到其他樹上的呢？就是最後遍歷出來的樹，它的根節點在步驟1的遍歷中離開時間最晚，而且可知它也是該樹中離開時間最晚的那個節點。這給我們提供了很好的選擇，在第一次深搜遍歷時，記錄時間i離開的頂點j，即numb[i]=j。那麼，我們每次只需找到沒有找過的頂點中具有最晚離開時間的頂點直接深搜(對於GT來説)就可以了。每次深搜都得到一個強連通分量。
隱藏性質:
分析到這裏，我們已經知道怎麼求強連通分量了。但是，應當注意到第二次深搜選擇樹的順序有一個特點。它就是：如果把求出來的每個強連通分量收縮成一個點，並且用求出每個強連通分量的順序來標記收縮後的節點，那麼這個順序其實就是強連通分量收縮成點後形成的有向無環圖的拓撲序列。為什麼呢？首先，應該明確搜索後的圖一定是有向無環圖呢？廢話，如果還有環，那麼環上的頂點對應的所有原來圖上的頂點構成一個強連通分量，而不是構成環上那麼多點對應的獨自的強連通分量了。然後就是為什麼是拓撲序列，我們在改進分析的時候，不是先選的樹不會連通到其他樹上（對於反圖GT來説），也就是後選的樹沒有連通到先選的樹，也即先出現的強連通分量收縮的點只能指向後出現的強連通分量收縮的點。那麼拓撲序列不是理所當然的嗎？這就是Kosaraju算法的一個隱藏性質。
代碼思路
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算法
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=record x,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算法
Gabow算法其實就是Tarjan算法的變形，我們觀察一下，只是它用第二個堆棧來輔助求出強連通分量的根，而不是Tarjan算法裏面的indx[]和mlik[]數組。那麼，我們説一下如何使用第二個堆棧來輔助求出強連通分量的根。
我們使用類比方法，在Tarjan算法中，每次mlik[i]的修改都是由於環的出現(不然，mlik[i]的值不可能變小)，每次出現環，在這個環裏面只剩下一個mlik[i]沒有被改變(深度最低的那個)，或者全部被改變，因為那個深度最低的節點在另一個環內。那麼Gabow算法中的第二堆棧變化就是刪除構成環的節點，只剩深度最低的節點，或者全部刪除，這個過程是通過出棧來實現，因為深度最低的那個頂點一定比前面的先訪問，那麼只要出棧一直到棧頂那個頂點的訪問時間不大於深度最低的那個頂點。其中每個被彈出的節點屬於同一個強連通分量。那有人會問：為什麼彈出的都是同一個強連通分量？因為在這個節點訪問之前，能夠構成強連通分量的那些節點已經被彈出了，這個對Tarjan算法有了解的都應該清楚，那麼Tarjan算法中的判斷根我們用什麼來代替呢？想想，其實就是看看第二個堆棧的頂元素是不是當前頂點就可以了。
其實Tarjan算法和Gabow算法其實是同一個思想的不同實現，但是，Gabow算法更精妙，時間更少(不用頻繁更新mlik[])。
代碼思路
步驟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;
}
Pascal
procedure 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算法要高。
