使用 C 代碼實現拓撲排序

1.介紹

自己之前並沒有接觸過拓撲排序，頂多聽說過拓撲圖。在寫前一篇文章的時候，看到 Abp 框架在處理模塊依賴項的時候使用了拓撲排序，來確保頂級節點始終是最先進行載入的。第一次看到覺得很神奇，看了一下維基百科頭也是略微大，自己的水平也是停留在冒泡排序的層次。ヽ(≧□≦)ノ

看了第二篇參考資料才大致了解，在此記錄一下。

2.原理

先來一個基本定義：

在圖論中，拓撲排序（Topological Sorting）是一個有向無環圖（DAG, Directed Acyclic Graph）的所有頂點的線性序列。且該序列必須滿足下面兩個條件：

• 每個頂點出現且只出現一次。
• 若存在一條從頂點 A 到頂點 B 的路徑，那麼在序列中頂點 A 出現在頂點 B 的前面。

有向無環圖（DAG）才有拓撲排序，非DAG圖沒有拓撲排序一說。

例如，有一個集合它的依賴關係如下圖：

可以看到他有一個依賴關係:

1. Module D 依賴於 Module E 與 Module B 。
2. Module E 依賴於 Module B 與 Module C 。
3. Module B 依賴於 Module A 與 Module C 。
4. Module C 依賴於 Module A 。
5. Module A 無依賴 。

這個就是一個 DAG 圖，我們要得到它的拓撲排序，一個簡單的步驟如下：

1. 從 DAG 圖中選擇一個沒有前驅的頂點並輸出。
2. 從 DAG 圖中刪除該頂點，以及以它為起點的有向邊。
3. 重複步驟 1、2 直到當前的 DAG 圖為空，或者

   當前圖不存在無前驅的頂點為止

   。

按照以上步驟，我們來進行一個排序試試。

最後的排序結果就是：

Module D -> Module E -> Module B -> Module C -> Module A

emmmm，其實一個有向無環圖可以有一個或者多個拓撲序列的，因為有的時候會存在一種情況，即以下這種情況：

這個時候你就可能會有這兩種結果

D->E->B->C->F->A

D->E->B->F->C->A

因為 F 與 C 是平級的，他們初始化順序即便不同也沒有什麼影響，因為他們的依賴層級是一致的，不過細心的朋友可能會發現這個順序好像是反的，我們還需要將其再反轉一次。

3.實現

上面這種方法僅適用於已知入度的時候，也就是說這些內容本身就是存在於一個有向無環圖之中的，如果按照以上方法進行拓撲排序，你需要維護一個入度為 0 的隊列，然後每次迭代移除入度為 0 頂點所指向的頂點入度。

例如有以下圖：

按照我們之前的演算法，

1. 首先初始化隊列，將 5 與 4 這兩個入度為 0 的頂點加入隊列當中。
2. 執行 While 循環，條件是隊列不為空。
3. 之後首先拿出 4 。
4. 然後針對其指向的頂點 0 與 頂點 1 的入度減去 1。
5. 減去指向頂點入度的時候同時判斷，被減去入度的頂點其值是否為 0 。
6. 這裡 1 入度被減去 1 ，為 0 ，添加到隊列。
7. 0 頂點入度減去 1 ，為 1。
8. 隊列現在有 5 與 1 這兩個頂點，循環判斷隊列不為空。
9. 5 指向的頂點 0 入度 減去 1，頂點 0 入度為 0 ，插入隊列。

這樣反覆循環，最終隊列全部清空，退出循環，得到拓撲排序的結果4, 5, 2, 0, 3, 1 。

4.深度優先搜索實現

在參考資料 1 的代碼當中使用的是深度優先演算法，它適用於有向無環圖。

有以下有向環圖 G2：

對上圖 G2 進行深度優先遍歷，首先從入度為 0 的頂點 A 開始遍歷：

它的步驟如下：

1. 訪問 A 。
2. 訪問 B 。
3. 訪問 C 。

在訪問了 B 後應該是訪問 B 的另外一個頂點，這裡可以是隨機的也可以是有序的，具體取決於你存儲的序列順序，這裡先訪問 C 。

1. 訪問 E 。
2. 訪問 D 。

這裡訪問 D 是因為 B 已經被訪問過了，所以訪問頂點 D 。

1. 訪問 F 。

因為頂點 C 已經被訪問過，所以應該回溯訪問頂點 B 的另一個有向邊指向的頂點 F 。

1. 訪問 G 。

因此最後的訪問順序就是 A -> B -> C -> E -> D -> F -> G ，注意順序還是不太對哦。

看起來跟之前的方法差不多，實現當中，其 Sort() 方法內部包含一個 visited 字典，用於標記已經訪問過的頂點，sorted 則是已經排序完成的集合列表。

在字典里 Key 是頂點的值，其 value 值用來標識是否已經訪問完所有路徑，為 true 則表示正在處理該頂點，為 false 則表示已經處理完成。

現在我們來寫實現吧：

結果：

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！