求強連通分量——Tarjan、Kosaraju算法 -开发者知识库

求強連通分量——Tarjan、Kosaraju算法 -开发者知识库,第1张

1、強連通分量

    有向圖強連通分量在有向圖G中,如果兩個頂點vi,vj間有一條從vi到vj的有向路徑,同時還有一條從vj到vi的有向路徑,則稱兩個頂點強連通(strongly connected)。如果有向圖G的每兩個頂點都強連通,稱G是一個強連通圖。有向圖的極大強連通子圖,稱為強連通分量(strongly connected components)。

2、求強連通分量

    目前有三種時間效率為O(N)的求強連通分量的算法,分別為Tarjan、Kosaraju和Gabow算法,其中Gabow算法很少被使用,這里只介紹前兩種算法。

3、Tarjan算法

    求有向圖的強連通分量,按照朴素的思路來做,可以分別求正向連通分量和反向連通分量,然后求交集。顯然時間效率達到O(N^2)。Tarjan算法有更好的辦法。

【算法思路】Tarjan算法是基於對圖深度優先搜索(dfs)的算法。遍歷搜索樹前先初始化low數組,用來記錄回路入口,即強連通分量的代表結點的時間戳。在用dfs遍歷搜索樹的時候,搜索樹中每個點分配一個時間戳,遍歷樹中遍歷到的點填寫時間戳和low數組值(都填當前時間)並入棧,如果遍歷到已經入棧的點,即出現回路,也就是找到了一個強連通分量,回溯時把回路中各點的low值置為回路入口的時間戳值。如果有新回路包含了舊回路,則新回路中各點的low值將被置為更小的時間戳值。完成整個搜索樹的遍歷后,搜索樹中各強連通分量已合並完畢,並以入口點的時間戳值進行了標記。

#include<vector>
using namespace std;

const int N = 1000;

vector<int> g[N], s; //鄰接表和遍歷樹用的棧
int n, low[N], dfn[N], t; //點數,low值數組,時間戳數組和當前時間
int sccID[N], sccNum; //點的scc歸屬數組和scc總數
bool inStack[N]; //標記點是否在棧內

void dfs(int v)
{
low[v] = dfn[v] = t; //填寫當前點的low值和時間戳值
s.push_back(v); //當前點入棧
inStack[v] = true; //入棧標記
for( int i = 0 ; i < g[v].size() ; i )
{
int u = g[v][i];
if( !dfn[u] ) //如果點還沒有遍歷過
{
dfs(u);
if( low[u] < low[v] )
low[v] = low[u]; //回溯時更新low值
}
else if( inStack[u] && dfn[u] < low[v] )
low[v] = dfn[u]; //如果找到了回路,更新low值
}
if( low[v] != dfn[v] ) //如果遍當前點不是強連通分量的入口
return;
int top;
do //強連通分量出棧
{
top = s.back();
inStack[top] = false;
sccID[top] = sccNum; //填寫點的強連通分量歸屬
s.pop_back();
}while( top != v );
sccNum ; //更新強連通分量數量
}

void Tarjan()
{
s.clear(); //初始化棧
for( int i = 0 ; i < n ; i )
dfn[i] = 0; //初始化時間戳
t = 0; //初始化當前時間
sccNum = 0; //初始化scc數
for( int i = 0 ; i < n ; i )
if(!dfn[i])
dfs(i); //遍歷所有點
}

4、Kosaraju算法

【算法原理】一個有向圖的強連通分量與其逆圖是一樣的(即假如任意頂點s與t屬於原圖中的一個強連通分量,那么在逆圖中這兩個頂點必定也屬於同一個強連通分量,這個事實由強連通性的定義可證)。Kosaraju的結論是,在第二次dfs中,同一棵搜索樹上的結點屬於一個強連通分量。

【算法步驟】

①在該圖的逆圖(所有邊做反向)上運行dfs,將頂點按照后序編號(后序遍歷:對一個結點來說先給其所有子結點依次編號,然后給其本身編號)的順序放入一個數組中(這個過程作用在DAG上得到的就是一個拓撲排序);

②在原圖上,按第一步得出的后序編號的逆序進行dfs。也就是說,在第二次dfs時,每次都挑選當前未訪問的結點中具有最大后序編號的頂點作為dfs樹的樹根。實際效果就是在原圖上按照逆圖中由根結點到子結點的遍歷順序依次建立遍歷樹進行遍歷。

(實際上原圖和逆圖顛倒一下結果並沒有什么不同)

【算法評價】Kosaraju算法雖然是線性的,但是需要兩次dfs,跟另外兩個著名的求解強連通分量的算法相比,這是一個劣勢。但是Kosaraju算法有個神奇之處在於:計算之后的強連通分量編號的順序( sccID[ topo[ i ] ] ),剛好是該有向圖K(D)(kernelDAG,核心DAG:將原圖中每個強連通分量縮成一個點形成的有向無環圖)的一個拓撲排序!因此Kosaraju算法同時提供了一個計算有向圖K(D)拓撲排序的線性算法。這個結果在一些應用中非常重要。

#include<cstring>
#include<vector>
using namespace std;

const int N = 1000;

vector<int> g[N], gn[N]; //建立原圖和逆圖
int n, t, topo[N]; //點數,當前遍歷時間和拓撲排序序列
int sccNum, sccID[N]; //scc數和點的scc歸屬
bool vis[N]; //標記訪問過的點

void dfs( int v ) //目的是遍歷所有點,建立后序遍歷的拓撲排序序列
{
if( vis[v] )
return;
vis[v] = true;
for( int i = 0 ; i < g[v].size() ; i )
if( !vis[g[v][i]] )
dfs(g[v][i]);
topo[t ] = v; //后序遍歷,回溯時根結點后進入拓撲序列
}
void ndfs( int v ) //反向遍歷拓撲序列
{
if( sccID[v] )
return;
sccID[v] = sccNum; //同一棵子樹上的點屬於同一個scc
for( i = 0 ; i < gn[v].size() ; i )
if( !id[gn[v][i]] )
ndfs(gn[v][i]);
}
void Kosaraju()
{
t = 0; //初始化當前時間
memset(vis,false,sizeof(vis)); //初始化訪問標記
for( int i = 0 ; i < n ; i ) //遍歷原圖建立拓撲序列
if( !vis[i] )
dfs(i);
sccNum = 0; //初始化scc數
for( int i = 0 ; i < n ; i )
sccID[i] = 0; //初始化點的scc歸屬
for( int i = t-1 ; i >= 0 ; i-- )//逆序遍歷拓撲序列
if( !sccID[topo[i]] )
{
sccNum ; //強連通分量編號不可以使用0,先自加
ndfs(topo[i]);
}
}
這兩個算法我就不特別寫鄰接矩陣版本的模板了。

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复