圖
拓撲排序
拓撲排序接收一個有向無環圖（DAG），把它的頂點排成一行，使每條邊都指向前方——若有一條從 A 到 B 的邊，那麼在排序中 A 就排在 B 前面。它在日常中的含義就是依賴解析：「先做這個，再做那個」。穿襪子必須在穿鞋之前；大學課程有先修要求；建置系統必須先編譯函式庫，再編譯用到它的程式。
它只對 DAG 有效：圖必須是有向的（箭頭說明誰必須先於誰）且無環的（沒有環）。環意味著 A 必須排在 B 前、B 又必須排在 A 前——這是一個不可能成立的矛盾要求，因此根本不存在合法的排序。正確的拓撲序通常不止一種，因為彼此之間沒有依賴關係的項目，相對位置可以互換。
兩種標準方法的時間都是 O(V + E)。Kahn 演算法反覆取出任何一個「已無入邊」（即沒有未滿足的依賴）的頂點並輸出它。DFS 方法跑一次深度優先搜尋，在每個頂點的遞迴結束時輸出它，最後把清單反轉。兩種方法都能給出合法的執行順序——而如果根本排不出順序，這本身就證明了圖中含有環。
queue<int> q;
for (int v = 0; v < n; ++v)
if (indeg[v] == 0) q.push(v);
while (!q.empty()) {
int v = q.front(); q.pop();
order.push_back(v);
for (int nb : adj[v])
if (--indeg[nb] == 0) q.push(nb);
}每移除一個頂點，就把它後繼的入度減一，從而「釋放」它們。
拓撲排序只對 DAG 有定義。排不出完整順序，正是偵測有向圖中環的標準辦法。
又稱
另見