拓撲排序
在電腦科學領域，有向圖的拓撲排序（英語：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