DFS應用——查找強分支

【0】README

0.1）本文總結于資料結構與算法分析，源代碼均為原創，旨在了解 “DFS應用——查找強分支” 的idea 并用源代碼加以實作；

【1】查找強分支

1.1）如何檢測一個圖是否是強連通的：通過執行兩次DFS，我們可以檢測一個有向圖是否是強連通的，如果它不是強連通的，那麼我們實際上可以得到頂點的一個子集，它們到其自身是強連通的；

1.2）首先，在輸入的圖G上執行一次 DFS。通過對深度優先生成森林的後序周遊将G的頂點編号，然後再把G 的所有邊反向，形成 Gr（如何建構 Gr）；

1.3）上述算法通過對 Gr 執行一次深度優先搜尋而完成，總是在編号最高的頂點開始一次新的DFS。于是，我們在頂點G 開始對 Gr 的DFS， G的編号為10。

1.4）但該頂點不通向任何頂點，是以下一次搜尋在H 點開始（以下查找強分支的過程僅僅是一個可能的case，僅舉例而已）。這次調用通路 I 和 J。下一次調用在B點開始并通路 A、C 和 F。此後的調用時 DFS（D）以及最終調用DFS（E）。

1.5）結果得到的深度優先生成森林如下圖所示：

1.6）對深度優先生成森林中的分析：

在該深度優先生成森林中的每棵樹形成一個強連通分支。對于我們的例子，這些強連通分支為 {G}， {H，I，J}， {B，A，C，F}，{D} 和 {E}；

1.7）為了了解上述算法為什麼成立？

1.7.1）首先，注意到，如果兩個頂點v 和 w 都在同一個強連通分支中，那麼在原圖G中就存在從 v到w 和從w到v的路徑，是以，在Gr中也存在。
1.7.2）現在，如果兩個頂點v 和 w 不在Gr的同一個深度優先生成樹中，那麼顯然它們也不可能在同一個強連通分支中；

【2】source code + printing results

2.1）download source code： https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter9/p249_dfs_strong_component

2.2）source code at a glance：（for complete code , please click the given link above）

// finding the strong component from the reverse graph and strongComponent derives from dfs
void strongComponent(Vertex vertex, int depth)
{
	int i;
	AdjTable temp;
	Vertex adjVertex;	
	
	//printf("
	 visited[%c] = 1 ", flag[vertex]);
	visited[vertex] = 1; // update visited status of vertex
	vertexIndex[vertex] = counter++; // number the vertex with counter
	temp = reverseAdj[vertex];	
		
	while(temp->next)
	{
		printf("   ");
		adjVertex = temp->next->vertex;		
		if(visited[adjVertex]) // judge whether the adjVertes was visited before		
		{
			if(vertexIndex[vertex] > vertexIndex[adjVertex] && parent[vertex] != adjVertex) 	
			{
				parent[adjVertex] = vertex; // building back side, attention of condition of building back side above
				
				// just for printing effect
				for(i = 0; i < depth; i++)  
					printf("      ");
				printf("v[%c]->v[%c] (backside) 
", flag[vertex], flag[adjVertex]);
			}
		}
		
		else
		{
			parent[adjVertex] = vertex;
			
			// just for printing effect
			for(i = 0; i < depth; i++)  
				printf("      ");
			printf("v[%c]->v[%c] (building edge)
", flag[vertex], flag[adjVertex]);			
			strongComponent(adjVertex, depth+1);
		}		
		temp = temp->next;		
	} 	
}

2.3）printing results：