摘要: 下面我先說以下拓撲排序：
嚴蔚敏《數據結構》上的定義是：由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。
直觀的說偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員之間均可比較。
拓撲排序的具體做法是：
1.在有向圖中選擇一個沒有前驅（入度為0）的頂點，輸出
2.從圖中刪除該頂點和所有以它為尾的弧，并更新相關點的入度
3.重復1，2步，直到所有頂點都被輸出，或者發現圖中存在回路。
閱讀全文
posted @
2012-08-16 19:19 小鼠標 閱讀(1806) |
評論 (0) |
編輯 收藏