【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("\n\t visited[%c] = 1 ", flag[vertex]);visited[vertex] = 1; // update visited status of vertexvertexIndex[vertex] = counter++; // number the vertex with countertemp = 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 effectfor(i = 0; i < depth; i++) printf(" ");printf("v[%c]->v[%c] (backside) \n", flag[vertex], flag[adjVertex]);}}else{parent[adjVertex] = vertex;// just for printing effectfor(i = 0; i < depth; i++) printf(" ");printf("v[%c]->v[%c] (building edge)\n", flag[vertex], flag[adjVertex]); strongComponent(adjVertex, depth+1);} temp = temp->next; } }

2.3）printing results：

總結

以上是生活随笔為你收集整理的DFS应用——查找强分支的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。