最關(guān)鍵通用部分：強(qiáng)連通分量一定是圖的深搜樹的一個(gè)子樹。
一、 Kosaraju算法
1. 算法思路
基本思路：
這個(gè)算法可以說是最容易理解，最通用的算法，其比較關(guān)鍵的部分是同時(shí)應(yīng)用了原圖G和反圖GT。(步驟1)先用對(duì)原圖G進(jìn)行深搜形成森林(樹)，（步驟2）然后任選一棵樹對(duì)其進(jìn)行深搜(注意這次深搜節(jié)點(diǎn)A能往子節(jié)點(diǎn)B走的要求是EAB存在于反圖GT)，能遍歷到的頂點(diǎn)就是一個(gè)強(qiáng)連通分量。余下部分和原來的森林一起組成一個(gè)新的森林，繼續(xù)步驟2直到 沒有頂點(diǎn)為止。
改進(jìn)思路：
當(dāng)然，基本思路實(shí)現(xiàn)起來是比較麻煩的(因?yàn)椴襟E2每次對(duì)一棵樹進(jìn)行深搜時(shí)，可能深搜到其他樹上去，這是不允許的，強(qiáng)連通分量只能存在單棵樹中(由開篇第一句話可知))，我們當(dāng)然不這么做，我們可以巧妙的選擇第二深搜選擇的樹的順序，使其不可能深搜到其他樹上去。想象一下，如果步驟2是從森林里選擇樹，那么哪個(gè)樹是不連通(對(duì)于GT來說)到其他樹上的呢？就是最后遍歷出來的樹，它的根節(jié)點(diǎn)在步驟1的遍歷中離開時(shí)間最晚，而且可知它也是該樹中離開時(shí)間最晚的那個(gè)節(jié)點(diǎn)。這給我們提供了很好的選擇，在第一次深搜遍歷時(shí)，記錄時(shí)間i離開的頂點(diǎn)j，即numb[i]=j。那么，我們每次只需找到?jīng)]有找過的頂點(diǎn)中具有最晚離開時(shí)間的頂點(diǎn)直接深搜(對(duì)于GT來說)就可以了。每次深搜都得到一個(gè)強(qiáng)連通分量。
隱藏性質(zhì):
分
析到這里，我們已經(jīng)知道怎么求強(qiáng)連通分量了。但是，大家有沒有注意到我們?cè)诘诙紊钏堰x擇樹的順序有一個(gè)特點(diǎn)呢？如果在看上述思路的時(shí)候，你的腦子在思
考，相信你已經(jīng)知道了！！！它就是：如果我們把求出來的每個(gè)強(qiáng)連通分量收縮成一個(gè)點(diǎn)，并且用求出每個(gè)強(qiáng)連通分量的順序來標(biāo)記收縮后的節(jié)點(diǎn)，那么這個(gè)順序其
實(shí)就是強(qiáng)連通分量收縮成點(diǎn)后形成的有向無環(huán)圖的拓?fù)湫蛄小槭裁茨兀渴紫龋瑧?yīng)該明確搜索后的圖一定是有向無環(huán)圖呢？廢話，如果還有環(huán)，那么環(huán)上的頂點(diǎn)對(duì)應(yīng)
的所有原來圖上的頂點(diǎn)構(gòu)成一個(gè)強(qiáng)連通分量，而不是構(gòu)成環(huán)上那么多點(diǎn)對(duì)應(yīng)的獨(dú)自的強(qiáng)連通分量了。然后就是為什么是拓?fù)湫蛄校覀冊(cè)诟倪M(jìn)分析的時(shí)候，不是先選
的樹不會(huì)連通到其他樹上（對(duì)于反圖GT來說），也就是后選的樹沒有連通到先選的樹，也即先出現(xiàn)的強(qiáng)連通分量收縮的點(diǎn)只能指向后出現(xiàn)的強(qiáng)連通分量收縮的點(diǎn)。那么拓?fù)湫蛄胁皇抢硭?dāng)然的嗎？這就是Kosaraju算法的一個(gè)隱藏性質(zhì)。
2. 偽代碼
Kosaraju_Algorithm:
step1：對(duì)原圖G進(jìn)行深度優(yōu)先遍歷，記錄每個(gè)節(jié)點(diǎn)的離開時(shí)間。
step2：選擇具有最晚離開時(shí)間的頂點(diǎn)，對(duì)反圖GT進(jìn)行遍歷，刪除能夠遍歷到的頂點(diǎn)，這些頂點(diǎn)構(gòu)成一個(gè)強(qiáng)連通分量。
step3：如果還有頂點(diǎn)沒有刪除，繼續(xù)step2，否則算法結(jié)束。
3. 實(shí)現(xiàn)代碼：
#include <iostream>
using namespace std;
const int MAXN = 110;
typedef int AdjTable[MAXN]; //鄰接表類型
int n;
bool flag[MAXN]; //訪問標(biāo)志數(shù)組
int belg[MAXN]; //存儲(chǔ)強(qiáng)連通分量,其中belg[i]表示頂點(diǎn)i屬于第belg[i]個(gè)強(qiáng)連通分量
int numb[MAXN]; //結(jié)束時(shí)間標(biāo)記,其中numb[i]表示離開時(shí)間為i的頂點(diǎn)
AdjTable adj[MAXN], radj[MAXN]; //鄰接表,逆鄰接表
//用于第一次深搜,求得numb[1..n]的值
void VisitOne(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]的值
void VisitTwo(int cur, int sig)
{
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算法,返回為強(qiáng)連通分量個(gè)數(shù)
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;
}
二、 Trajan算法
1. 算法思路：
這
個(gè)算法思路不難理解，由開篇第一句話可知，任何一個(gè)強(qiáng)連通分量，必定是對(duì)原圖的深度優(yōu)先搜索樹的子樹。那么其實(shí)，我們只要確定每個(gè)強(qiáng)連通分量的子樹的根，
然后根據(jù)這些根從樹的最低層開始，一個(gè)一個(gè)的拿出強(qiáng)連通分量即可。那么身下的問題就只剩下如何確定強(qiáng)連通分量的根和如何從最低層開始拿出強(qiáng)連通分量了。
那么如何確定強(qiáng)連通分量的根，在這里我們維護(hù)兩個(gè)數(shù)組，一個(gè)是indx[1..n]，一個(gè)是mlik[1..n]，其中indx[i]表示頂點(diǎn)i開始訪問時(shí)間，mlik[i]為與頂點(diǎn)i鄰接的頂點(diǎn)未刪除頂點(diǎn)j的mlik[j]和mlik[i]的最小值(mlik[i]初始化為indx[i])。這樣，在一次深搜的回溯過程中，如果發(fā)現(xiàn)mlik[i]==indx[i]那么，當(dāng)前頂點(diǎn)就是一個(gè)強(qiáng)連通分量的根，為什么呢？因?yàn)槿绻皇菑?qiáng)連通分量的跟，那么它一定是屬于另一個(gè)強(qiáng)連通分量，而且它的根是當(dāng)前頂點(diǎn)的祖宗，那么存在包含當(dāng)前頂點(diǎn)的到其祖宗的回路，可知mlik[i]一定被更改為一個(gè)比indx[i]更小的值。
至于如何拿出強(qiáng)連通分量，這個(gè)其實(shí)很簡(jiǎn)單，如果當(dāng)前節(jié)點(diǎn)為一個(gè)強(qiáng)連通分量的根，那么它的強(qiáng)連通分量一定是以該根為根節(jié)點(diǎn)的(剩下節(jié)點(diǎn))子
樹。在深度優(yōu)先遍歷的時(shí)候維護(hù)一個(gè)堆棧，每次訪問一個(gè)新節(jié)點(diǎn)，就壓入堆棧。現(xiàn)在知道如何拿出了強(qiáng)連通分量了吧？是的，因?yàn)檫@個(gè)強(qiáng)連通分量時(shí)最先被壓人堆棧
的，那么當(dāng)前節(jié)點(diǎn)以后壓入堆棧的并且仍在堆棧中的節(jié)點(diǎn)都屬于這個(gè)強(qiáng)連通分量。當(dāng)然有人會(huì)問真的嗎？假設(shè)在當(dāng)前節(jié)點(diǎn)壓入堆棧以后壓入并且還存在，同時(shí)它不屬
于該強(qiáng)連通分量，那么它一定屬于另一個(gè)強(qiáng)連通分量，但當(dāng)前節(jié)點(diǎn)是它的根的祖宗，那么這個(gè)強(qiáng)連通分量應(yīng)該在此之前已經(jīng)被拿出。現(xiàn)在沒有疑問了吧，那么算法介
紹就完了。
2. 偽代碼：
Tarjan_Algorithm:
step1:
找一個(gè)沒有被訪問過的節(jié)點(diǎn)v，goto step2(v)。否則，算法結(jié)束。
step2(v):
初始化indx[v]和mlik[v]
對(duì)于v所有的鄰接頂點(diǎn)u：
1) 如果沒有訪問過，則step2(u),同時(shí)維護(hù)mlik[v]
2) 如果訪問過，但沒有刪除，維護(hù)mlik[v]
如果indx[v]==mlik[v]，那么輸出相應(yīng)的強(qiáng)連通分量
3. 實(shí)現(xiàn)代碼
#include <iostream>
using namespace std;
const int MAXN = 110;
const char NOTVIS = 0x00; //頂點(diǎn)沒有訪問過的狀態(tài)
const char VIS = 0x01; //頂點(diǎn)訪問過,但沒有刪除的狀態(tài)
const char OVER = 0x02; //頂點(diǎn)刪除的狀態(tài)
typedef int AdjTable[MAXN]; //鄰接表類型
int n;
char flag[MAXN]; //用于標(biāo)記頂點(diǎn)狀態(tài),狀態(tài)有NOTVIS,VIS,OVER
int belg[MAXN]; //存儲(chǔ)強(qiáng)連通分量,其中belg[i]表示頂點(diǎn)i屬于第belg[i]個(gè)強(qiáng)連通分量
int stck[MAXN]; //堆棧,輔助作用
int mlik[MAXN]; //很關(guān)鍵,與其鄰接但未刪除頂點(diǎn)地最小訪問時(shí)間
int indx[MAXN]; //頂點(diǎn)訪問時(shí)間
AdjTable adj[MAXN]; //鄰接表
//深搜過程,該算法的主體都在這里
void Visit(int cur, int &sig, int &scc_num)
{
int i;
stck[++stck[0]] = cur; flag[cur] = VIS;
mlik[cur] = indx[cur] = ++sig;
for ( i=1; i<=adj[cur][0]; ++i )
{
if ( NOTVIS==flag[adj[cur][i]] )
{
Visit(adj[cur][i],sig,scc_num);
if ( mlik[cur]>mlik[adj[cur][i]] )
{
mlik[cur] = mlik[adj[cur][i]];
}
}
else if ( VIS==flag[adj[cur][i]] )
{
if ( mlik[cur]>indx[adj[cur][i]] ) //該部分的indx應(yīng)該是mlik,但是根據(jù)算法的屬性,使用indx也可以,且時(shí)間更少
{
mlik[cur] = indx[adj[cur][i]];
}
}
}
if ( mlik[cur]==indx[cur] )
{
++ scc_num;
do
{
belg[stck[stck[0]]] = scc_num;
flag[stck[stck[0]]] = OVER;
}
while ( stck[stck[0]--]!=cur );
}
}
//Tarjan算法,求解belg[1..n],且返回強(qiáng)連通分量個(gè)數(shù),
int Tarjan_StronglyConnectedComponent()
{
int i, sig, scc_num;
memset(flag+1,NOTVIS,sizeof(char)*n);
sig = 0; scc_num = 0; stck[0] = 0;
for ( i=1; i<=n; ++i )
{
if ( NOTVIS==flag[i] )
{
Visit(i,sig,scc_num);
}
}
return scc_num;
}
三、 Gabow算法
1. 思路分析
這個(gè)算法其實(shí)就是Tarjan算法的變異體，我們觀察一下，只是它用第二個(gè)堆棧來輔助求出強(qiáng)連通分量的根，而不是Tarjan算法里面的indx[]和mlik[]數(shù)組。那么，我們說一下如何使用第二個(gè)堆棧來輔助求出強(qiáng)連通分量的根。
我們使用類比方法，在Tarjan算法中，每次mlik[i]的修改都是由于環(huán)的出現(xiàn)(不然，mlik[i]的值不可能變小)，每次出現(xiàn)環(huán)，在這個(gè)環(huán)里面只剩下一個(gè)mlik[i]沒有被改變(深度最低的那個(gè))，或者全部被改變，因?yàn)槟莻€(gè)深度最低的節(jié)點(diǎn)在另一個(gè)環(huán)內(nèi)。那么Gabow算
法中的第二堆棧變化就是刪除構(gòu)成環(huán)的節(jié)點(diǎn)，只剩深度最低的節(jié)點(diǎn)，或者全部刪除，這個(gè)過程是通過出棧來實(shí)現(xiàn)，因?yàn)樯疃茸畹偷哪莻€(gè)頂點(diǎn)一定比前面的先訪問，那
么只要出棧一直到棧頂那個(gè)頂點(diǎn)的訪問時(shí)間不大于深度最低的那個(gè)頂點(diǎn)。其中每個(gè)被彈出的節(jié)點(diǎn)屬于同一個(gè)強(qiáng)連通分量。那有人會(huì)問：為什么彈出的都是同一個(gè)強(qiáng)連
通分量？因?yàn)樵谶@個(gè)節(jié)點(diǎn)訪問之前，能夠構(gòu)成強(qiáng)連通分量的那些節(jié)點(diǎn)已經(jīng)被彈出了，這個(gè)對(duì)Tarjan算法有了解的都應(yīng)該清楚，那么Tarjan算法中的判斷根我們用什么來代替呢？想想，其實(shí)就是看看第二個(gè)堆棧的頂元素是不是當(dāng)前頂點(diǎn)就可以了。
現(xiàn)在，你應(yīng)該明白其實(shí)Tarjan算法和Gabow算法其實(shí)是同一個(gè)思想的不同實(shí)現(xiàn)，但是，Gabow算法更精妙，時(shí)間更少(不用頻繁更新mlik[])。
2. 偽代碼
Gabow_Algorithm:
step1:
找一個(gè)沒有被訪問過的節(jié)點(diǎn)v，goto step2(v)。否則，算法結(jié)束。
step2(v):
將v壓入堆棧stk1[]和stk2[]
對(duì)于v所有的鄰接頂點(diǎn)u：
1) 如果沒有訪問過，則step2(u)
2) 如果訪問過，但沒有刪除，維護(hù)stk2[](處理環(huán)的過程)
如果stk2[]的頂元素==v，那么輸出相應(yīng)的強(qiáng)連通分量
3. 實(shí)現(xiàn)代碼
#include <iostream>
using namespace std;
const int MAXN = 110;
typedef int AdjTable[MAXN]; //鄰接表類型
int n;
int intm[MAXN]; //標(biāo)記進(jìn)入頂點(diǎn)時(shí)間
int belg[MAXN]; //存儲(chǔ)強(qiáng)連通分量,其中belg[i]表示頂點(diǎn)i屬于第belg[i]個(gè)強(qiáng)連通分量
int stk1[MAXN]; //輔助堆棧
int stk2[MAXN]; //輔助堆棧
AdjTable adj[MAXN]; //鄰接表
//深搜過程,該算法的主體都在這里
void Visit(int cur, int &sig, int &scc_num)
{
int i;
intm[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],且返回強(qiáng)連通分量個(gè)數(shù),
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;
}
四、 總結(jié)
寫到這里，做一個(gè)總結(jié)：Kosaraju算法的第二次深搜隱藏了一個(gè)拓?fù)湫再|(zhì)，而Tarjan算法和Gabow算法省略了第二次深搜，所以，它們不具有拓?fù)湫再|(zhì)。Tarjan算法用堆棧和標(biāo)記，Gabow用兩個(gè)堆棧（其中一個(gè)堆棧的實(shí)質(zhì)是代替了Tarjan算法的標(biāo)記部分）來代替Kosaraju算法的第二次深搜，所以只用一次深搜，效率比Kosaraju算法高。