5.4 DAG 的拓撲排序

動機

不少排程問題並非要求一個數值最優解，而是要找出任何一個合法次序。修讀 某科之前要先完成所有先修科；編譯某個模組之前要先處理它依賴的模組；穿鞋之 前要先穿襪。部分工作彼此沒有依賴，先後次序便可以互換。

有向圖正好表達這種限制：頂點代表工作，邊 u->v 表示 u 必須排在 v 之前。拓撲排序把每條局部先後關係整合成一個全域線性序列。我們需要回答四個 問題：次序何時存在、為何可能不唯一、怎樣有效建構，以及演算法失敗時如何確 認圖中有有向環。

Tutorial 10 提供兩個互補觀點。Kahn 演算法由「所有前置條件已完成」的 頂點向前建構；DFS 方法則在頂點完成時才放入答案，從反向完成次序得到結 果。兩者都不只是排序程序，也同時是有向環偵測程序。

實際系統往往會把輸出次序交給下一個處理階段，所以漏掉頂點的部分序列並不 是小格式問題，而是一個不能執行的錯誤排程。

定義

定義

有向無環圖

有向圖 G=(V,E) 的每條邊都是有次序的二元組 (u,v)。若存在 v_0->v_1->...->v_k->v_0，便有一個有向環。沒有任何有向環的有向圖稱為 有向無環圖（directed acyclic graph，DAG）。

方向不可忽略。u->v 是由 u 指向 v 的單向限制，並不自動包含反方向。 所以無向圖中的環與這裏所說的有向環並非同一概念。

定義

拓撲序

G=(V,E) 的拓撲序是一個恰好包含每個頂點一次的序列，而且對每條邊 u->v，u 都必須出現在 v 之前。若 pos(x) 表示位置，就是每條邊都要 令 pos(u) 嚴格小於 pos(v)。

拓撲序未必唯一。若 x 與 y 之間沒有任何方向的可達關係，圖可能沒有規定 兩者誰先誰後。演算法遇到多個同時合法的選擇時，採用不同 tie-breaking 便會 得到不同但同樣正確的答案。

定義

入度、源點與鄰接表

indegree[v] 是進入 v 的邊數；入度為零的頂點稱為源點。鄰接表 adj[u] 只列出所有由 u 指向的後繼頂點。

兩個演算法都需要由已選頂點沿出邊前進，因此鄰接表比每次掃描整行鄰接矩陣 更合適。DFS 偵測環時還要分清三種狀態：未標記、在當前遞迴路徑上的暫時標 記，以及連同所有後繼都已完成的永久標記。遇到暫時標記，表示一條邊返回當 前路徑上的祖先，因而閉合成有向環。

定理 / 命題

定理

拓撲序存在當且僅當圖是 DAG

有向圖若包含有向環，就沒有拓撲序；反過來，每個有限 DAG 都至少有一個拓撲 序。

關鍵結構是：每個非空有限 DAG 都有源點。若每個頂點都有入邊，任選一點後不 斷沿入邊向後走；由於頂點數有限，最終必會重複頂點，形成有向環。因此 DAG 必有可安全放在首位的源點；移除它後仍是 DAG，可以重複同一論證。

定理

Kahn 演算法的處理數判準

Kahn 演算法輸出全部 |V| 個頂點，當且僅當輸入圖是 DAG。若零入度容器已 空，但輸出數 k 小於 |V|，未處理子圖必定含有向環。

所以實作不能把部分序列當作成功結果；必須把已輸出數量與總頂點數比較。

定理

反向 DFS 完成次序是拓撲序

若 DFS 沒有遇到指向暫時標記頂點的邊，每個頂點完成時把它加入答案最前端， 最後所得序列便是拓撲序。

這裏必須使用完成時刻，而不是首次發現時刻。另一種等價做法是在完成時 push 入 stack，整個 DFS 完結後再反轉。

證明思路

有向環為何不可能排序

假設有環 v_0->v_1->...->v_k->v_0。每條邊都要求下一個位置嚴格較大， 沿環走一圈便會要求 pos(v_0) 嚴格小於自身，矛盾。這並不只表示某一幅圖 中有一支箭向左，而是任何線性排列都至少違反環上的一條邊。

Kahn 不變量與正確性

維持不變量：indegree[v] 等於尚未輸出頂點指向 v 的邊數。開始時掃 描所有邊一次計算入度；輸出 u 時只掃 adj[u]，並把每個後繼的入度減一。 某頂點首次降至零，正代表它的全部前驅已輸出，因此把它接到答案尾端不會違 反任何邊。

KAHN(adj, V):
    indegree[v] = 0 for every v
    for each u in V:
        for each v in adj[u]: indegree[v] += 1
    S = all v with indegree[v] == 0
    order = empty list
    while S is not empty:
        remove one u from S
        append u to order
        for each v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0: insert v into S
    if length(order) != |V|: return error directed cycle
    return order

若仍有頂點而 S 已空，剩餘有限子圖沒有源點；按上述結構事實，它不可能是 DAG。S 可以是 queue、stack、set 或 priority queue，選擇只影響回傳哪一 個合法次序，不影響正確性。

DFS 標記、完成邏輯與正確性

暫時標記的頂點恰好是當前 recursion stack。若 u->v 指向暫時標記的 v， stack 已給出路徑 v->...->u，新邊把它閉合成環。指向永久標記則安全，因為 v 已完成並已放入答案。

若沒有環，考慮任意邊 u->v。當 u 準備完成時，v 要麼由這次 DFS 遞迴 完成，要麼早已永久完成；兩種情況下 v 都已在答案中。此時把 u 加到最 前，便保證 u 在 v 之前。這個論證對每條邊成立。

DFS-TOPO(adj, V):
    mark[v] = UNMARKED for every v
    order = empty list
    for each v in V:
        if mark[v] == UNMARKED: VISIT(v)
    return order

VISIT(u):
    if mark[u] == TEMPORARY: abort with error directed cycle
    if mark[u] == PERMANENT: return
    mark[u] = TEMPORARY
    for each v in adj[u]: VISIT(v)
    mark[u] = PERMANENT
    add u to the front of order

鄰接表複雜度

Kahn 初始化陣列及找源點需 O(V)；計算與更新入度時，每個鄰接表項目只被 掃描常數次，共 O(E)，所以 queue 或 stack 版本總時間是 O(V+E)。DFS 同樣只啟動每個頂點一次、檢查每條出邊一次，故也是 O(V+E)。兩者在圖儲 存以外都需 O(V) 輔助空間。若改用鄰接矩陣，每個頂點都要掃描 V 個可能 鄰居，即使圖很稀疏也會是 O(V^2)。

例題詳解

例題

檢查次序及看見非唯一性

Tutorial 10 的圖有邊 A->B, A->D, B->C, B->D, C->D, C->E, C->F, D->E。 A,B,C,D,E,F 與 A,B,C,D,F,E 都合法，因為沒有邊限制 E 與 F 的 相對次序。A,B,C,E,D,F 則不合法，因為 D->E 的尾端反而較後。檢查拓 撲序要看所有圖邊，不能只看序列中相鄰的頂點。

例題

Tutorial 10 圖的完整 Kahn trace

初始入度為 A:0, B:1, C:1, D:3, E:2, F:1。依 tutorial 的分支選擇，狀 態如下：

步驟	取出	入度更新	之後可選	輸出
起點	—	—	{A}	空
1	A	B:1->0, D:3->2	{B}	A
2	B	C:1->0, D:2->1	{C}	A,B
3	C	D:1->0, E:2->1, F:1->0	{D,F}	A,B,C
4	F	無	{D}	A,B,C,F
5	D	E:1->0	{E}	A,B,C,F,D
6	E	無	空	A,B,C,F,D,E

六個頂點全部輸出，結果有效。第三步後也可先選 D；這個分支正是多個拓撲 序的具體來源。

例題

同一幅圖的完整 DFS 完成 trace

由 B 開始，並按 tutorial 的 F,E,D 次序檢查 C 的後繼。完成事件依次 令前置答案變為：

完成頂點	加到最前後的答案
F	F
E	E,F
D	D,E,F
C	C,D,E,F
B	B,C,D,E,F

外層迴圈之後遇到未標記的 A；其後繼 B,D 已永久完成，所以 A 可直接 完成並加到最前，得到 A,B,C,D,E,F。加入最前的次序與完成次序相反。

例題

兩種方法如何揭示同一個環

在 tutorial 圖加入 E->B，便有 B->C->E->B（亦同時有較長的 B->C->D->E->B）。Kahn 只能移除 A，其後尚有五點但沒有零入度點，故 報告有環。DFS 由 B 暫時標記 C，先完成 F，再按既定 F,E,D 次序暫時 標記 E；E 指回仍有暫時標記的 B 時，立即報告 B->C->E->B。此刻 D 尚未被訪問。兩者都不可把部分答案當成成功排序。

常見錯誤

常見錯誤

只檢查序列中的相鄰點

合法性要求每條 u->v 都令 u 較早；並非只要大部分箭向前，或相鄰項看來 合理就足夠。

常見錯誤

每輪重新計算所有入度

應先算一次入度，移除 u 時再沿 adj[u] 精確遞減。反覆掃描全圖會破壞線 性時間界限。

常見錯誤

忘記檢查 Kahn 的輸出數

容器變空只有在全部頂點已輸出時才代表成功；否則剩餘子圖有環。

常見錯誤

DFS 只用一個 visited bit

已見過的頂點可能仍在當前路徑，也可能早已完成。只有前者證明有環，因此要分 暫時與永久標記。

常見錯誤

DFS 在發現時便加入答案

正確規則是在完成時加到最前，或完成時 push 並最後反轉；發現次序沒有這個保 證。

總結

• 拓撲序恰好包含每個頂點一次，並尊重每條有向邊。
• 有拓撲序當且僅當圖是 DAG；有向環會產生互相矛盾的先後要求。
• Kahn 維持剩餘入度並反覆輸出零入度點；輸出少於 |V| 便證明有環。
• DFS 以未標記、暫時、永久三種狀態偵測環，並用反向完成次序排序。
• 不同 tie-breaking 或 DFS 探索次序可產生不同但同樣合法的答案。
• 使用鄰接表時，兩種方法都是 O(V+E) 時間及額外 O(V) 空間。

練習

思考檢查

1. Tutorial 10 圖中，Kahn 先後輸出 A、B 後，C、D、E、F 的剩餘入度各是多少？下一個可選誰？

只更新從已移除頂點發出的邊。

思考檢查

2. 一幅有 9 個頂點的圖只輸出 7 點後，零入度容器便變空。Kahn 可以作出甚麼結論？

比較處理數與總頂點數。

思考檢查

3. DFS 遇到指向永久標記 v 的邊 u->v，是否已證明有環？它與指向暫時標記有何分別？

永久標記表示 v 的遞迴呼叫已返回。

思考檢查

4. 只有 P->R 與 Q->R，而 P、Q 之間沒有路徑。寫出兩個拓撲序並解釋。

兩個前置點都要早於 R，但彼此不互相限制。

思考檢查

5. 不靠背誦，從鄰接表迴圈說明 Kahn 為何是 O(V+E)。

數初始頂點工作，以及每個鄰接項被讀取的次數。

答案與解答

解答 · 解答 1

移除 A 後，B 可選而 D 降至二；再移除 B，C 由一降至零，D 由二降至一。因此為 C:0, D:1, E:2, F:1，下一個只能選 C。

解答 · 解答 2

圖含有向環。剩餘兩點所在的子圖沒有源點；七點的部分序列不是原九點圖的完 整拓撲序。

解答 · 解答 3

不是。永久標記表示 v 已完成，不代表它仍在當前路徑。暫時標記則表示 stack 已有 v->...->u 的路徑，加入 u->v 就閉合成有向環。

解答 · 解答 4

P,Q,R 與 Q,P,R 都合法。兩者都把 P,Q 放在 R 之前，而圖沒有規定 P,Q 的相對次序。

解答 · 解答 5

初始化與找源點是 O(V)。計算入度時每條邊讀一次；主迴圈中每個頂點最多取 出一次，每條出邊再更新一次，共 O(V+E)。相加後仍是 O(V+E)。