基本介紹
- 中文名:Kosaraju算法
- 外文名:Kosaraju's algorithm
- 提出者:S. Rao Kosaraju
- 提出時間:1978
- 套用學科:計算機科學
- 適用領域範圍:圖論 ACM編程
算法思想,偽代碼,c++代碼,
算法思想
Kosaraju算法的解釋和實現都比較簡單,為了找到強連通分支,首先對圖G運行DFS,計算出各頂點完成搜尋的時間f;然後計算圖的逆圖GT,對逆圖也進行DFS搜尋,但是這裡搜尋時頂點的訪問次序不是按照頂點標號的大小,而是按照各頂點f值由大到小的順序;逆圖DFS所得到的森林即對應連通區域。具體流程如圖(1~4)。
上面我們提及原圖G的逆圖GT,其定義為GT=(V,ET),ET={(u,v):(v,u)∈E}}。也就是說GT是由G中的邊反向所組成的,通常也稱之為圖G的轉置。在這裡值得一提的是,逆圖GT和原圖G有著完全相同的連通分支,也就說,如果頂點s和t在G中是互達的,若且唯若s和t在GT中也是互達的。
為了方便大家理解,附下引用部落格中的例圖:
![原圖 原圖](/img/e/b40/nBnauYmZhNWOkJjNxQWYwQjZ4czNwUTOwUzY4UTOkFjNwUmN4AzY0EDM4E2LptWa39yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
![原圖進行dfs 原圖進行dfs](/img/5/270/nBnauImMxIGM1kTZ3gTYzMjZ5MjZwAjM2UWNxMDZ2MTZjVTMhVWOjVjYhVzLptWa39yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
上面是第一次dfs
![逆圖 逆圖](/img/b/1ed/nBnauMTO1U2YxMjY0QmY4MzNkJjMlRGZzYWOhF2N2MDOxYDO5EDOmFTNxI2LptWa39yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
![逆圖dfs,獲得強連通分量 逆圖dfs,獲得強連通分量](/img/b/6c4/nBnauITY4QjM4MWOlR2MilDMyQ2N1UDM5ETZ1QTNkR2MykDM0UTO0MTMhN2LptWa39yYpB3LltWahJ2Lt92YuUHZpFmYuMmczdWbp9yL6MHc0RHa.jpg)
偽代碼
- 對原圖G進行深度優先遍歷,記錄每個節點的離開時間num[i]
- 如果還有頂點沒有刪除,繼續步驟2,否則算法結束
c++代碼
#include <bits/stdc++.h> /* Kosaraju求強連通分量鄰接矩陣 */ using namespace std; int map[511][511];int nmap[511][511];int visited[501];stack<int>S;int N;int DFS1(int v) /* visitedthevnode */{ visited[v] = 1; for (int i = 1;i <= N;i++) if (!visited[i] && map[v][i]) DFS1( i ); S.push( v ); return 0;}int DFS2( int v ){ visited[v] = 1; for (int i = 1;i <= N;i++) if ( !visited[i] && nmap[v][i] ) DFS2( i ); return 0;}int kosaraju(){ while (!S.empty()) S.pop(); memset(visited,0,sizeof(visited)); for (int i = 1;i <= N;i++) if (!visited[i]) DFS1( i ); int t = 0; memset(visited,0,sizeof(visited)); while (!S.empty()) { int v = S.top(); S.pop(); print f( "|%d|", v ); if (!visited[v]) { t++; DFS2( v ); } } return t;}int main(){ int M,s,e; scanf("%d%d",&N,&M); memset(map,0,sizeof(map) ); memset(nmap,0,sizeof(nmap) ); for (int i = 0; i < M; i++) { scanf("%d%d",&s,&e); map[s][e] = 1; nmap[e][s] = 1; } printf("%d\n", kosaraju()); /* 輸出連通分量個數 */ return0;}
551221233441
樣例輸出:
2