拓撲排序
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在電腦科學領域,有向圖的拓撲排序(英語:Topological sorting)或拓撲定序(英語:Topological ordering)是對其頂點的一種線性排序,使得對於從頂點到頂點的每個有向邊,在排序中都在之前。
例如,圖形的頂點可以表示要執行的任務,並且邊可以表示一個任務必須在另一個任務之前執行的約束;在這個應用中,拓撲排序只是一個有效的任務順序。
若且唯若圖中沒有定向環時(即有向無環圖),才有可能進行拓撲排序。
任何有向無環圖至少有一個拓撲排序。已知有演算法可以在線性時間內,構建任何有向無環圖的拓撲排序。
在圖論中,由一個有向無環圖的頂點組成的序列,若且唯若滿足下列條件時,才能稱為該圖的一個拓撲排序:
- 序列中包含每個頂點,且每個頂點只出現一次;
- 若A在序列中排在B的前面,則在圖中不存在從B到A的路徑。
演算法
[編輯]卡恩演算法
[編輯]卡恩於1962年提出了該演算法 [1]。簡單來說,假設L是存放結果的列表,先找到那些入度為零的節點,把這些節點放到L中,因為這些節點沒有任何的父節點。然後把與這些節點相連的邊從圖中去掉,再尋找圖中的入度為零的節點。對於新找到的這些入度為零的節點來說,他們的父節點已經都在L中了,所以也可以放入L。重複上述操作,直到找不到入度為零的節點。如果此時L中的元素個數和節點總數相同,說明排序完成;如果L中的元素個數和節點總數不同,說明原圖中存在環,無法進行拓撲排序。
L ← 包含已排序的元素的列表,目前为空 S ← 入度为零的节点的集合 当 S 非空时: 将节点n从S移走 将n加到L尾部 选出任意起点为n的边e = (n,m),移除e。如m没有其它入边,则将m加入S。 重复上一步。 如图中有剩余的边则: return error (图中至少有一个环) 否则: return L (L为图的拓扑排序)
深度優先搜尋
[編輯]另一種拓撲排序的方法運用了深度優先搜尋。深度優先搜尋以任意順序迴圈遍歷圖中的每個節點。若搜尋進行中碰到之前已經遇到的節點,或碰到葉節點,則中止演算法。
L ← 一个空的 用来存放已排序的节点的列表 当图中存在未永久标记的节点时: 选出任何未永久标记的节点n visit(n) function visit(节点 n) 如n被永久标记: return 如n被临时标记: stop (不是定向无环图,至少有一个环) 将n临时标记 对于每一个以n为起点的边(n,m): visit(m) 去掉n的临时标记 将n永久标记 在L的起始位置插入n(如L已有内容 后移它们以空出起始位置)
這種拓撲排序的方法被首次公開於Tarjan的著作中[2]。
例子
[編輯]在某校的選課系統中,存在這樣的規則:每門課可能有若干門先修課,如果要修讀某一門課,則必須要先修讀此課程所要求的先修課後才能修讀。假設一個學生同時只能修讀一門課程,那麼,被選課系統允許的他修完他需要所有課程的順序是一個拓撲序。
在這個例子中,每一門課程對應有向圖中的一個頂點,每一個先修關係對應一條有向邊(從先修課指向需要先修課的課)。
參考資料
[編輯]- ^ Kahn, Arthur B., Topological sorting of large networks, Communications of the ACM, 1962, 5 (11): 558–562, S2CID 16728233, doi:10.1145/368996.369025
- ^ Tarjan, Robert E., Edge-disjoint spanning trees and depth-first search, Acta Informatica, 1976, 6 (2): 171–185, S2CID 12044793, doi:10.1007/BF00268499
外部連結
[編輯]- NIST Dictionary of Algorithms and Data Structures: topological sort (頁面存檔備份,存於互聯網檔案館)
- 埃里克·韋斯坦因. TopologicalSort. MathWorld.
|
|