-
kosaraju算法
鎖定
Aho, Hopcroft 和Ullman相信這個算法是由S. Rao Kosaraju在1978在一個未發表的論文上提出的。
相同的算法還從Micha Sharir 1981年自己出版的書上被單獨的發現，這個算法利用了一個事實，即轉置圖（同圖中的每邊的方向相反）具有和原圖完全一樣的強連通分量。
- 中文名
- Kosaraju算法
- 外文名
- Kosaraju's algorithm
- 提出者
- S. Rao Kosaraju
- 提出時間
- 1978年
- 適用領域
- 圖論 ACM 編程
- 應用學科
- 計算機科學 數據結構
kosaraju算法算法思想
Kosaraju算法的解釋和實現都比較簡單，為了找到強連通分支，首先對圖G運行DFS，計算出各頂點完成搜索的時間f；然後計算圖的逆圖GT，對逆圖也進行DFS搜索，但是這裏搜索時頂點的訪問次序不是按照頂點標號的大小，而是按照各頂點f值由大到小的順序；逆圖DFS所得到的森林即對應連通區域。具體流程如圖(1~4)
[1]
。
上面我們提及原圖G的逆圖GT，其定義為GT=(V,ET)，ET={(u,v):(v,u)∈E}}。也就是説GT是由G中的邊反向所組成的，通常也稱之為圖G的轉置。在這裏值得一提的是，逆圖GT和原圖G有着完全相同的連通分支，也就説，如果頂點s和t在G中是互達的，當且僅當s和t在GT中也是互達的。
為了方便大家理解，附下引用博客中的例圖：
圖1 原圖
圖2 原圖進行dfs
上面是第一次dfs
圖3 逆圖
圖4 逆圖dfs，獲得強連通分量
kosaraju算法偽代碼
- 對原圖G進行深度優先遍歷，記錄每個節點的離開時間num[i]
- 如果還有頂點沒有刪除，繼續步驟2，否則算法結束
kosaraju算法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;
}
55 12 21 23 34 41
樣例輸出：
2
- 參考資料
-
- 1. 強連通分支算法 ．cn博客[引用日期2014-08-09]
