有向無環圖的拓樸排序（topological ordering of a DAG）

有些事必須先於其他事發生：先穿襪子才穿鞋、先編譯函式庫才能編譯用它的程式、先修先修課才能修進階課。從每個任務畫一個箭頭指向依賴它的任務，你就得到一張有向圖。拓樸排序是把所有任務排成一行的方式，使每個箭頭都指向前方——沒有任何任務出現在它所依賴的東西之前。它回答的是「我能以什麼順序做完這一切而不違反任何依賴？」。

這樣的排序恰當有向圖沒有環時存在——也就是 DAG，有向無環圖。（一個環會意味某任務必須先於它自己，那在一行裡無法排出。）產生它有兩種標準方法。卡恩法：反覆找一個沒有入邊的頂點（沒有任何它必須等待的東西），輸出它，並把它連同它的出邊一起刪除；每個頂點的入邊數隨著進行而維護。DFS 法更俐落：跑 DFS，當一個頂點完成（它所有後代都做完了）時，把它推到一個串列的最前端；把這個完成串列由前往後讀，就是一個有效的拓樸排序。為何 DFS 完成順序行得通？因為在 DAG 中沒有回邊，所以對每條邊 u->v，v 都比 u 先完成——意味 u 在 v 之後被推到最前端，於是 u 在最終順序中落在 v 之前，恰如箭頭所要求。兩種方法都跑在 O(n + m)。

拓樸排序是建置系統、任務排程器、試算表重算，以及 DAG 上動態規劃的骨幹（它給出填入狀態的順序，使依賴都已就緒）。兩個誠實的要點。第一，排序通常不唯一——當數個任務彼此獨立時，它們之間的任何順序都行，所以一張 DAG 可以有許多個有效的拓樸排序。第二，若你在一張有環的圖上跑拓樸排序演算法，它無法完成：卡恩法會在還有頂點剩下時就用光了零入邊的頂點，而那個剩下的集合正是環存在的見證。所以拓樸排序在有向圖上兼具環測試的功能。