首先,介紹一下有向無環圖,
從字面上理解:
- 為有向圖
- 無環
舉例,
-
- 有向的二叉樹是特殊的有向無環圖,
-
- 如圖(關鍵部分)

對于有向圖來說,深度優先遍歷下,若從head出發到結束時出現一條從head的下級節點mid開始指向head的一條路徑,則必定此圖有環,
拓撲排序
- 首先,拓撲排序的物件肯定是有向無環圖中左右的點,
- 其次,若存在路徑從a指向b,則拓撲排序結果中a一定在b的前面,
- 最后,拓撲排序的排序規則(沒有那么抽象),依次將入度為零的點拿出去,并抹掉它的出度線,

有圖為例
經過第一次篩選得 A

第二次篩選得 B

第三次篩選得D

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

最后一個是F
所以綜上,拓撲排序為 A B D CF E
好,簡單明了,幫助理解概念,代碼還是要自己敲哦,嘿嘿嘿,
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/114588.html
標籤:其他
