最關鍵通用部分：強連通分量一定是圖的深搜樹的一個子樹。

 

一、     Kosaraju算法

1.      算法思路

基本思路：

這個算法可以說是最容易理解，最通用的算法，其比較關鍵的部分是同時應用了原圖G和反圖G^T。(步驟1)先用對原圖G進行深搜形成森林(樹)，（步驟2）然后任選一棵樹對其進行深搜(注意這次深搜節點A能往子節點B走的要求是E_AB存在于反圖G^T)，能遍歷到的頂點就是一個強連通分量。余下部分和原來的森林一起組成一個新的森林，繼續步驟2直到 沒有頂點為止。

改進思路：

當然，基本思路實現起來是比較麻煩的(因為步驟2每次對一棵樹進行深搜時，可能深搜到其他樹上去，這是不允許的，強連通分量只能存在單棵樹中(由開篇第一句話可知))，我們當然不這么做，我們可以巧妙的選擇第二深搜選擇的樹的順序，使其不可能深搜到其他樹上去。想象一下，如果步驟2是從森林里選擇樹，那么哪個樹是不連通(對于G^T來說)到其他樹上的呢？就是最后遍歷出來的樹，它的根節點在步驟1的遍歷中離開時間最晚，而且可知它也是該樹中離開時間最晚的那個節點。這給我們提供了很好的選擇，在第一次深搜遍歷時，記錄時間i離開的頂點j，即numb[i]=j。那么，我們每次只需找到沒有找過的頂點中具有最晚離開時間的頂點直接深搜(對于G^T來說)就可以了。每次深搜都得到一個強連通分量。 

隱藏性質:

    分 析到這里，我們已經知道怎么求強連通分量了。但是，大家有沒有注意到我們在第二次深搜選擇樹的順序有一個特點呢？如果在看上述思路的時候，你的腦子在思 考，相信你已經知道了！！！它就是：如果我們把求出來的每個強連通分量收縮成一個點，并且用求出每個強連通分量的順序來標記收縮后的節點，那么這個順序其 實就是強連通分量收縮成點后形成的有向無環圖的拓撲序列。為什么呢？首先，應該明確搜索后的圖一定是有向無環圖呢？廢話，如果還有環，那么環上的頂點對應 的所有原來圖上的頂點構成一個強連通分量，而不是構成環上那么多點對應的獨自的強連通分量了。然后就是為什么是拓撲序列，我們在改進分析的時候，不是先選 的樹不會連通到其他樹上（對于反圖GT來說），也就是后選的樹沒有連通到先選的樹，也即先出現的強連通分量收縮的點只能指向后出現的強連通分量收縮的點。那么拓撲序列不是理所當然的嗎？這就是Kosaraju算法的一個隱藏性質。 

2.      偽代碼

Kosaraju_Algorithm:

 step1：對原圖G進行深度優先遍歷，記錄每個節點的離開時間。

 step2：選擇具有最晚離開時間的頂點，對反圖GT進行遍歷，刪除能夠遍歷到的頂點，這些頂點構成一個強連通分量。

 step3：如果還有頂點沒有刪除，繼續step2，否則算法結束。 

3.      實現代碼：

#include <iostream>

using namespace std;

 

const int MAXN = 110;

 

typedef int AdjTable[MAXN]; //鄰接表類型

 

int      n;

bool     flag[MAXN]; //訪問標志數組

int      belg[MAXN]; //存儲強連通分量,其中belg[i]表示頂點i屬于第belg[i]個強連通分量

int      numb[MAXN]; //結束時間標記,其中numb[i]表示離開時間為i的頂點

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算法,返回為強連通分量個數

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.      算法思路：

這 個算法思路不難理解，由開篇第一句話可知，任何一個強連通分量，必定是對原圖的深度優先搜索樹的子樹。那么其實，我們只要確定每個強連通分量的子樹的根， 然后根據這些根從樹的最低層開始，一個一個的拿出強連通分量即可。那么身下的問題就只剩下如何確定強連通分量的根和如何從最低層開始拿出強連通分量了。

那么如何確定強連通分量的根，在這里我們維護兩個數組，一個是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]更小的值。

至于如何拿出強連通分量，這個其實很簡單，如果當前節點為一個強連通分量的根，那么它的強連通分量一定是以該根為根節點的(剩下節點)子 樹。在深度優先遍歷的時候維護一個堆棧，每次訪問一個新節點，就壓入堆棧。現在知道如何拿出了強連通分量了吧？是的，因為這個強連通分量時最先被壓人堆棧 的，那么當前節點以后壓入堆棧的并且仍在堆棧中的節點都屬于這個強連通分量。當然有人會問真的嗎？假設在當前節點壓入堆棧以后壓入并且還存在，同時它不屬 于該強連通分量，那么它一定屬于另一個強連通分量，但當前節點是它的根的祖宗，那么這個強連通分量應該在此之前已經被拿出。現在沒有疑問了吧，那么算法介 紹就完了。 

2.      偽代碼：

Tarjan_Algorithm:

   step1:

   找一個沒有被訪問過的節點v，goto step2(v)。否則，算法結束。

      step2(v):

       初始化indx[v]和mlik[v]

       對于v所有的鄰接頂點u：

              1)     如果沒有訪問過，則step2(u),同時維護mlik[v]

              2)     如果訪問過，但沒有刪除，維護mlik[v]

       如果indx[v]==mlik[v]，那么輸出相應的強連通分量 

3.      實現代碼

#include <iostream>

using namespace std;

 

const int  MAXN    = 110;

const char NOTVIS  = 0x00;   //頂點沒有訪問過的狀態

const char VIS     = 0x01;   //頂點訪問過,但沒有刪除的狀態

const char OVER    = 0x02;   //頂點刪除的狀態

 

typedef int AdjTable[MAXN];  //鄰接表類型

 

int      n;

char     flag[MAXN];         //用于標記頂點狀態,狀態有NOTVIS,VIS,OVER

int      belg[MAXN];         //存儲強連通分量,其中belg[i]表示頂點i屬于第belg[i]個強連通分量

int      stck[MAXN];         //堆棧,輔助作用

int      mlik[MAXN];         //很關鍵,與其鄰接但未刪除頂點地最小訪問時間

int      indx[MAXN];         //頂點訪問時間

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應該是mlik,但是根據算法的屬性,使用indx也可以,且時間更少

          {

             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],且返回強連通分量個數,

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.      思路分析

這個算法其實就是Tarjan算法的變異體，我們觀察一下，只是它用第二個堆棧來輔助求出強連通分量的根，而不是Tarjan算法里面的indx[]和mlik[]數組。那么，我們說一下如何使用第二個堆棧來輔助求出強連通分量的根。

我們使用類比方法，在Tarjan算法中，每次mlik[i]的修改都是由于環的出現(不然，mlik[i]的值不可能變小)，每次出現環，在這個環里面只剩下一個mlik[i]沒有被改變(深度最低的那個)，或者全部被改變，因為那個深度最低的節點在另一個環內。那么Gabow算 法中的第二堆棧變化就是刪除構成環的節點，只剩深度最低的節點，或者全部刪除，這個過程是通過出棧來實現，因為深度最低的那個頂點一定比前面的先訪問，那 么只要出棧一直到棧頂那個頂點的訪問時間不大于深度最低的那個頂點。其中每個被彈出的節點屬于同一個強連通分量。那有人會問：為什么彈出的都是同一個強連 通分量？因為在這個節點訪問之前，能夠構成強連通分量的那些節點已經被彈出了，這個對Tarjan算法有了解的都應該清楚，那么Tarjan算法中的判斷根我們用什么來代替呢？想想，其實就是看看第二個堆棧的頂元素是不是當前頂點就可以了。

現在，你應該明白其實Tarjan算法和Gabow算法其實是同一個思想的不同實現，但是，Gabow算法更精妙，時間更少(不用頻繁更新mlik[])。 

2.      偽代碼

Gabow_Algorithm:

           step1:

     找一個沒有被訪問過的節點v，goto step2(v)。否則，算法結束。

           step2(v):

            將v壓入堆棧stk1[]和stk2[]

            對于v所有的鄰接頂點u：

  1)     如果沒有訪問過，則step2(u)

  2)     如果訪問過，但沒有刪除，維護stk2[](處理環的過程)

            如果stk2[]的頂元素==v，那么輸出相應的強連通分量 

3.      實現代碼

#include <iostream>

using namespace std;

 

const int MAXN = 110;

 

typedef int AdjTable[MAXN]; //鄰接表類型

 

int      n;

int      intm[MAXN]; //標記進入頂點時間

int      belg[MAXN]; //存儲強連通分量,其中belg[i]表示頂點i屬于第belg[i]個強連通分量

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],且返回強連通分量個數,

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;

} 

 

四、  總結

    寫到這里，做一個總結：Kosaraju算法的第二次深搜隱藏了一個拓撲性質，而Tarjan算法和Gabow算法省略了第二次深搜，所以，它們不具有拓撲性質。Tarjan算法用堆棧和標記，Gabow用兩個堆棧（其中一個堆棧的實質是代替了Tarjan算法的標記部分）來代替Kosaraju算法的第二次深搜，所以只用一次深搜，效率比Kosaraju算法高。