有向無環圖的拓撲排序

• 2019 年 12 月 26 日
• 筆記

首先，介紹一下有向無環圖。

從字面上理解:

1. 為有向圖
2. 無環

舉例，

• 1. 有向的二叉樹是特殊的有向無環圖。
• 1. 如圖（關鍵部分）

對於有向圖來說，深度優先遍歷下，若從head出發到結束時出現一條從head的下級節點mid開始指向head的一條路徑，則必定此圖有環。

拓撲排序

• 首先，拓撲排序的對象肯定是有向無環圖中左右的點。
• 其次，若存在路徑從a指向b，則拓撲排序結果中a一定在b的前面。
• 最後，拓撲排序的排序規則（沒有那麼抽象），依次將入度為零的點拿出去，並抹掉它的出度線。

有圖為例

經過第一次篩選得 A

第二次篩選得 B

第三次篩選得D

第四次篩選的 C，F（若無特殊要求，C,F的順序是隨機的）（這裡我們按照字母表來）

最後一個是F 所以綜上，拓撲排序為 A B D CF E 好，簡單明了，幫助理解概念，程式碼還是要自己敲哦，嘿嘿嘿。