拓撲排序

在計算機科學領域，有向圖的拓撲排序（英語：Topological sorting）或拓撲定序（英語：Topological ordering）是對其頂點的一種線性排序，使得對於從頂點$u$到頂點$v$的每個有向邊$uv$，$u$在排序中都在$v$之前。

例如，圖形的頂點可以表示要執行的任務，並且邊可以表示一個任務必須在另一個任務之前執行的約束；在這個應用中，拓撲排序只是一個有效的任務順序。

當且僅當圖中沒有定向環時（即有向無環圖），才有可能進行拓撲排序。

任何有向無環圖至少有一個拓撲排序。已知有算法可以在線性時間內，構建任何有向無環圖的拓撲排序。

在圖論中，由一個有向無環圖的頂點組成的序列，當且僅當滿足下列條件時，才能稱為該圖的一個拓撲排序：

1. 序列中包含每個頂點，且每個頂點只出現一次；
2. 若A在序列中排在B的前面，則在圖中不存在從B到A的路徑。

算法

卡恩算法

卡恩於1962年提出了該算法 。簡單來說，假設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的著作中。

例子

在某校的選課系統中，存在這樣的規則：每門課可能有若干門先修課，如果要修讀某一門課，則必須要先修讀此課程所要求的先修課後才能修讀。假設一個學生同時只能修讀一門課程，那麼，被選課系統允許的他修完他需要所有課程的順序是一個拓撲序。

在這個例子中，每一門課程對應有向圖中的一個頂點，每一個先修關係對應一條有向邊（從先修課指向需要先修課的課）。

外部連結

• NIST Dictionary of Algorithms and Data Structures: topological sort （頁面存檔備份，存於網際網路檔案館）
• 埃里克·韋斯坦因. TopologicalSort. MathWorld.