1,在有向圖G中，如果兩個頂點間至少存在一條路徑，稱兩個頂點強連通(strongly connected)。如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。非強連通圖有向圖的極大強連通子圖，稱為強連通分量(strongly connected component)。
2,下圖中，子圖{1,2,3,4}為一個強連通分量，因為頂點1,2,3,4兩兩可達。{5},{6}也分別是兩個強連通分量。
3,Tarjan算法是基于對圖深度優先搜索的算法，每個強連通分量為搜索樹中的一棵子樹。搜索時，把當前搜索樹中未處理的節點加入一個堆棧，回溯時可以判斷棧頂到棧中的節點是否為一個強連通分量。
定義幾個關鍵數組:
int DFN[MAX]; //記錄節點u第一次被訪問時的步數
int LOW[MAX]; //記錄與節點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)。
4,實例代碼:
- #include<iostream> ??
- #include<vector> ??
- using ? namespace ?std; ??
- ??
- const ? int ?MAX=10001; ??
- ??
- int ?Stop; //棧中的元素個數 ??
- int ?cnt; //記錄連通分量的個數 ??
- int ?visitNum; //記錄遍歷的步數 ??
- int ?DFN[MAX];? //記錄節點u第一次被訪問時的步數 ??
- int ?LOW[MAX];? //記錄與節點u和u的子樹節點中最早的步數 ??
- bool ?instack[MAX]; //記錄節點u是否在棧中 ??
- int ?Stap[MAX]; //棧 ??
- int ?Belong[MAX]; //記錄每個節點屬于的強連通分量編號 ??
- ??
- int ?N; //節點個數 ??
- ??
- vector< int >?tree[MAX]; ??
- ??
- void ?tarjan( int ?i) ??
- { ??
- ???? int ?j; ??
- ????DFN[i]=LOW[i]=++visitNum; ??
- ????instack[i]= true ; ??
- ????Stap[++Stop]=i; //將當前節點壓入棧中 ??
- ???? for ?(unsigned?k=0;k<tree[i].size();k++) ??
- ????{ ??
- ????????j=tree[i][k]; ??
- ???????? if ?(!DFN[j])? //j還沒有被訪問過 ??
- ????????{ ??
- ????????????tarjan(j); ??
- ???????????? //父節點是子節點的子節點 ??
- ???????????? if ?(LOW[j]<LOW[i]) ??
- ????????????????LOW[i]=LOW[j]; ??
- ????????} ??
- ???????? //與j相連,但是j已經被訪問過,且還在棧中 ??
- ???????? //用子樹節點更新節點第一次出現的時間 ??
- ???????? else ? if ?(instack[j]?&&?DFN[j]<LOW[i]) ??
- ????????????LOW[i]=DFN[j]; ??
- ????} ??
- ???? //節點i是強連通分量的根 ??
- ???? if ?(DFN[i]==LOW[i]) ??
- ????{ ??
- ????????cnt++; ??
- ???????? //輸出找到的強連通分量 ??
- ????????cout<< "連通分量" <<cnt<< ":?" ; ??
- ???????? //退棧,直至找到根為止 ??
- ???????? do ??
- ????????{ ??
- ????????????j=Stap[Stop--]; ??
- ????????????instack[j]= false ; ??
- ????????????cout<<j<< "?" ; ??
- ????????????Belong[j]=cnt; ??
- ????????} ??
- ???????? while ?(j!=i); ??
- ????????cout<<endl; ??
- ????} ??
- } ??
- void ?solve() ??
- { ??
- ????Stop=cnt=visitNum=0; ??
- ????memset(DFN,0, sizeof (DFN)); ??
- ???? for ?( int ?i=1;i<=N;i++) ??
- ???????? if ?(!DFN[i]) //有可能圖不是連通圖 ??
- ????????????tarjan(i); ??
- } ??
- ??
- int ?main() ??
- { ??
- ????N=6; ??
- ????tree[1].push_back(3); ??
- ????tree[1].push_back(2); ??
- ????tree[2].push_back(4); ??
- ????tree[3].push_back(5); ??
- ????tree[3].push_back(4); ??
- ????tree[4].push_back(1); ??
- ????tree[4].push_back(6); ??
- ????tree[5].push_back(6); ??
- ????solve(); ??
- ???? for ( int ?i=1;i<=N;i++) ??
- ????????cout<<Belong[i]<< "?" ; ??
- ????cout<<endl; ??
- ???? return ?0; ??
- }??
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
