C#中怎么實現拓撲排序

這篇文章給大家介紹 C#中怎么實現拓撲排序，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

.原理

先來一個基本定義：

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

1. 每個頂點出現且只出現一次。

2. 若存在一條從頂點 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 則表示已經處理完成。

現在我們來寫實現吧：

結果：

關于 C#中怎么實現拓撲排序就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。