有向圖的強連通元件Strongly Connected Component

/ timbian

強連通元件(Strongly Connected Component)

在一張有向圖中，如果任兩個不同頂點a、b雙向都存在路徑時(即從a可以到b、從b可以到a)，我們稱這個圖為強連通圖。一個強連通元件(SCC)指的是一張有向圖G中的極大強連通子圖G’。

SCC

(取自演算法筆記)

我們可以發現，一個強連通元件是由一個或多個有向環組成的。所以要是把原圖G的各個強連通元件，各自收縮成一個點後，如此圖上就不會有環，原圖G就將會變成一張有向無環圖(DAG)。這樣問題就變得容易處理了!

 

求有向圖的強連通元件(SCC)有兩個常見的方法，分別是Tarjan演算法及Kosaraju演算法。

Tarjan’s Algorithm

求有向圖的強連通元件(SCC)的Tarjan演算法是由其發明者Robert Tarjan命名的，值得一提的是，Robert Tarjan還發明了求無向圖的雙連通元件的Tarjan演算法，以及求最近共同祖先(LCA)的離線Tarjan演算法，實在佩服這位前輩。

Tarjan演算法基本上利用了一個SCC的性質：一個SCC是由一個或多個環組成的。

SCC Tarjan

(取自Great Power Law)

以上圖舉例，假如從b點開始進行DFS遍歷，每遍歷一個點就給它一個時間戳記，則順序為b(1)->c(2)->d(3)->e(4)->a(5)。而a點有一條回邊連向已經遍歷過的b點，此時會將b點的時間戳記傳給a點，並依序往上傳給e、d、c，最後，環中所有節點的時間戳記都變成最早遍歷的節點b的，於是相同時間戳記的節點就屬於同一個SCC了。Tarjan演算法的基本思想就是如此，而時間複雜度等於一次DFS的時間。

Reference:

http://www.csie.ntnu.edu.tw/~u91029/Component.html#4

https://www.byvoid.com/blog/scc-tarjan

https://greatpowerlaw.wordpress.com/2013/05/05/scc-tarjans-algorithm/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
#define N 100001

vector<int> edge[N];
int dfn[N];
int low[N];
int T; //時間戳記 

stack<int> Stack;
bool instack[N];

int component[N]; //每個點對應到的 強連通元件收縮成的點
int C; //強連通元件個數 

int n;

void DFS(int u)
{

	dfn[u] = low[u] = ++ T;
	Stack.push(u);
	instack[u] = true;

	for(int i = 0; i < edge[u].size(); i ++)
	{
		int v = edge[u][i];

		if(!dfn[v])
		{
			DFS(v);
			low[u] = min(low[u], low[v]);
		}
		else if(instack[v])
			low[u] = min(low[u], dfn[v]); 

	}

	if(dfn[u] == low[u])
	{
		int t;

		C ++;

		do
		{
			t = Stack.top(); Stack.pop();
			instack[t] = false;
			component[t] = C;

		}while(t != u);

	}
}

void Tarjan()
{
	for(int i = 1; i <= n; i ++)
	{
		dfn[i] = 0;
		instack[i] = false;
	}
	while(Stack.size()) Stack.pop();

	T = 0;
	C = 0;

	for(int u = 1; u <= n; u ++)
	{
		if(!dfn[u])
			DFS(u);
	}
}

不難發現，這與求無向圖雙連通元件(或者割點、橋)的Tarjan演算法有很大的關聯性，兩者可以互相比較。

 

Kosaraju’s Algorithm

相較於Tarjan演算法，Kosaraju演算法的核心是：原圖顛倒所有邊的方向後得到的新圖，其所有的SCC和原圖的完全相同。

Kosaraju演算法要進行兩次DFS(第二次的DFS可改為BFS)，所以時間複雜度比Tarjan演算法差了些，但同樣為線性時間。這裡提供詳細說明的連結，請自行參考。

Reference:

http://www.csie.ntnu.edu.tw/~u91029/Component.html#5

https://greatpowerlaw.wordpress.com/2013/05/03/scc-kosarajus-algorithm/

 

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 30

vector<int> Edge[N];
vector<int> rEdge[N];
bool visit[N];
vector<int> order;
vector<int> scc[N];
int C;

int n;

void DFS1(int u)
{
	visit[u] = true;
	
	for(int i = 0; i < Edge[u].size(); i ++)
	{
		int v = Edge[u][i];
		if(!visit[v])
			DFS1(v);
	}
	
	order.push_back(u);
}

void DFS2(int u)
{
	visit[u] = true;
	scc[C].push_back(u);
	
	for(int i = 0; i < rEdge[u].size(); i ++)
	{
		int v = rEdge[u][i];
		if(!visit[v])
			DFS2(v);
	}
}

void Kosaraju()
{
	order.clear();
	for(int i = 1; i <= n; i ++)
		visit[i] = false;
		
	for(int u = 1; u <= n; u ++)
		if(!visit[u])
			DFS1(u);
	
	for(int i = 1; i <= n; i ++)
		visit[i] = false;
	C = 0;
		
	for(int i = n - 1; i >= 0; i --)
	{
		int u = order[i];
		if(!visit[u])
		{
			C ++;
			scc[C].clear();
			
			DFS2(u);	
		}
	}
	
}

發表留言