強連通成分Tarjanアルゴリズム

数日の强い连通の成分を见て、やはりあまり理解することができなくて、今日の午前中に队长に闻いて、、、Tarjanアルゴリズムに対して1つの理解があって、、特に1篇の良い文章を回転して、详しくTarjanアルゴリズムを绍介しました...
BYVoidオリジナル[有向図強連通成分]有向図Gでは、2つの頂点間に少なくとも1つの経路が存在する場合、2つの頂点強連通(strongly connected)と呼ばれる.図Gの各頂点に強い連通がある場合、Gは強い連通図と呼ばれる.非強連通図は、強連通成分(strongly conneted components)と呼ばれる方向図の極大強連通サブ図である.下図では、サブマップ{1,2,3,4}は、頂点1,2,3,4の2つが達できるため、強い連通成分である.{5},{6}もそれぞれ2つの強い連通成分である.直接定義に基づいて,交差を双方向に遍歴する方法で強い連通成分を求め,時間複雑度はO(N^2+M)であった.より良い方法はKosarajuアルゴリズムまたはTarjanアルゴリズムであり,両者の時間的複雑さはO(N+M)である.本論文ではTarjanアルゴリズムを紹介する.[Tarjanアルゴリズム]Tarjanアルゴリズムは、図の深さを優先的に検索するアルゴリズムに基づいており、各強い連通成分は、検索ツリー内の1本のサブツリーである.検索時には、現在の検索ツリーで処理されていないノードをスタックに追加し、遡及するとスタックの頂点からスタックのノードが強い連通成分であるかどうかを判断できます.DFN(u)をノードu検索の順序番号(タイムスタンプ)とし、Low(u)をuまたはuのサブツリーが遡及できる最も古いスタック内のノードのサブシーケンス番号として定義する.定義から、
?
Download download.txt

1
2
3
4
5
6

Low(u)=Min
{
    DFN(u),
    Low(v),(u,v)    ，u v    
    DFN(v),(u,v)           (    )
}

DFN(u)=Low(u)の場合,uをルートとする探索サブツリー上のすべてのノードは強い連通成分である.アルゴリズムの擬似コードは以下の通りです.
?
Download download.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

tarjan(u)
{
	DFN[u]=Low[u]=++Index                      //    u       Low  
	Stack.push(u)                              //    u    
	for each (u, v) in E                       //       
		if (v is not visted)               //     v     
			tarjan(v)                  //      
			Low[u] = min(Low[u], Low[v])
		else if (v in S)                   //     v    
			Low[u] = min(Low[u], DFN[v])
	if (DFN[u] == Low[u])                      //     u        
		repeat
			v = S.pop                  //  v  ，            
			print v
		until (u== v)
}

次にアルゴリズムフローの説明です.ノード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}を構成することが分かった.これでアルゴリズムは終了する.このアルゴリズムにより,図中のすべての3つの強い連通成分{1,3,4,2},{5},{6}を求めた.Tarjanアルゴリズムを実行する過程で,各頂点は1回アクセスされ,スタックは1回のみ出入りし,エッジは1回のみアクセスされるため,このアルゴリズムの時間的複雑度はO(N+M)であることが分かった.方向図の強い連通成分を求めてもう一つの強力なアルゴリズムがあり,Kosarajuアルゴリズムである.Kosarajuは有向図とその逆図を2回DFSする方法に基づいており,その時間的複雑さもO(N+M)である.TrajanアルゴリズムよりもKosarajuアルゴリズムの方が少し直感的かもしれません.しかしTarjanは原図に対して一度だけDFSを行い,逆図を確立することなくより簡潔である.実際のテストでは,Tarjanアルゴリズムの実行効率もKosarajuアルゴリズムより30%程度高かった.また,このTarjanアルゴリズムは,無方向図の二重連通成分(割点,ブリッジ)を求めるTarjanアルゴリズムとも深く関連している.このTarjanアルゴリズムを学習することは,二重連通成分を求めるTarjanアルゴリズムを深く理解するのに役立ち,両者を類比し,組み合わせて理解することができる.図への強い連通成分を求めるTarjanアルゴリズムは、その発明者Robert Tarjanによって命名された.Robert Tarjanはまた、二重連通成分を求めるTarjanアルゴリズムと、最近の共通祖先を求めるオフラインTarjanアルゴリズムを発明し、ここでTarjanに崇高な敬意を表した.附:tarjanアルゴリズムのC++プログラム
?
Download download.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

void tarjan(int i)
{
	int j;
	DFN[i]=LOW[i]=++Dindex;
	instack[i]=true;
	Stap[++Stop]=i;
	for (edge *e=V[i];e;e=e->next)
	{
		j=e->t;
		if (!DFN[j])
		{
			tarjan(j);
			if (LOW[j]<LOW[i])
				LOW[i]=LOW[j];
		}
		else if (instack[j] && DFN[j]<LOW[i])
			LOW[i]=DFN[j];
	}
	if (DFN[i]==LOW[i])
	{
		Bcnt++;
		do
		{
			j=Stap[Stop--];
			instack[j]=false;
			Belong[j]=Bcnt;
		}
		while (j!=i);
	}
}
void solve()
{
	int i;
	Stop=Bcnt=Dindex=0;
	memset(DFN,0,sizeof(DFN));
	for (i=1;i<=N;i++)
		if (!DFN[i])
			tarjan(i);
}