拓撲排序

復習

1、偏序：自反、反對稱、傳遞 全序：偏序且?a,b∈A$/forall a,b /in A$必有aRb或bRa 2、若以圖中的頂點來表示活動，有向邊表示活動之間的優先關系，則這種用頂點表示活動的有向圖成為AOV網（activity on vertex network）. 3、樹的存儲： （1）樹的順序存儲（先序序列+每個結點的度數） （2）雙親鏈表表示法 （3）孩子表示法

拓撲有序序列

在AOV網的偏序集合下構造一個全序的拓撲序列

注意

（1） 若圖中存在環，則不能是頂點滿足拓撲序列 （2）一個DAG（directed acyclic graph）可能有多個拓撲序列

無前驅的頂點優先的拓撲排序算法

（1）選擇沒有前驅的結點輸出它 （2）刪除該點，并刪去從該點出發的全部有向邊 （3） 重復上述兩步，直到不存在沒有前驅的結點

無后繼的頂點優先拓撲排序方法

可用逆鄰接表作為G的存儲結構

利用深度優先搜索遍歷對DAG拓撲排序