拓樸排序 Topological Sort

拓樸排序是一種幫一張圖上的節點做線性排序的演算法。對於一張有向無環圖中的所有節點 \(V(G) = \{v_1,v_2,...,v_{|V|}\}\)，排出一個序列，使所有有向邊 \((u,v) \in E(G)\) 在序列中 \(u\) 必排在 \(v\) 之前

為什麼需要拓樸排序?

為什麼會需要這個演算法呢? 可以考慮以下問題:

引入情境

已知資工系有 \(10\) 門課程:

課程 1	課程 2	課程 3	課程 4	課程 5
計算機概論	電腦網路	離散數學	微積分	演算法

課程 6	課程 7	課程 8	課程 9	課程 10
深度學習	機率論	資料結構	計算機組織	數位邏輯

每一門課程都有優先修習的順序，如下圖

以上圖為例，如果想要修習「演算法」，就得先修「資料結構」… 以此類推
如果某大一新生想排修課順序把 \(10\) 門課都修完，該如何排安排才能符合以上規則呢?

解法

我們把問題拆解一下:
假設我只想修「資料結構」，那麼先決條件就是需要先修完「離散數學」與「計算機概論」

在此問題中，其中一種合理的順序是:
計算機概論、微積分、離散數學、數位邏輯、資料結構、計算機組織、演算法、電腦網路、機率論、深度學習

當然，我們也可以發現答案不只一種，像是以下也可以是一種解答:
微積分、計算機概論、離散數學、數位邏輯、資料結構、計算機組織、演算法、電腦網路、機率論、深度學習

小結

這個問題相當簡單，看一下就能知道答案。因為它只有 \(10\) 門課，在圖論而言，就是 \(10\) 個節點

但是如果今天問題變成有 \(10^{6}\) 個節點呢? 這顯然需要一套「規則」去解決這個問題

介紹

目標

拓樸排序可以為一張是 \(dag\) 的圖 \(G\) 排出適當的走訪路徑，使對於 \(G\) 的所有邊 \((u,v)\)，\(u\) 必出現在 \(v\) 之前

輸入/輸出

• 輸入為一張 \(dag\)
• 輸出則為一個陣列，紀錄節點的順序

備註

• 拓樸排序以 \(dag\) 作為輸入，這是一個定理，在機制的部分會詳細說明
• \(dag\) 為有向無環圖 directed acyclic graph 的簡稱

拓樸???

沒有，這一點拓樸學也沒有。在古早時代的「拓樸」一詞涵蓋的非常廣泛，基本上只要是非數字或幾何的東西都可能被冠上拓樸之稱。早期的圖論也被認為是拓樸學的內容，而現在則不一定。像是拓樸排序所排的節點順序就不是基於數字的大小關係，因此才會有「拓樸」二字出現

原理說明

觀察 1: 入度與 \(dag\) 的關係

對於 \(G\) 的所有邊 \((u,v)\)，\(u\) 必出現在 \(v\) 之前。因此必須最先選擇入度為 \(0\) 的節點，因為入度為 \(0\) 的節點沒有任何邊通往此節點

接下來要走訪鄰居節點，但是要怎麼走訪呢? 可以試著把已走訪過的節點從圖上「刪除」，如此一來，就會有新的入度為 \(0\) 的節點了

以下圖為例
我們可以將 \(a\) 刪除，如此一來就知道接下來要走訪 \(b\) 與 \(c\)，因為 \(b\) 與 \(c\) 的入度為 \(0\)

⭣

入度: 對於一有向圖，設一節點 \(v\)，則 \(v\) 的入度即為所有通往 \(v\) 的邊數

觀察 2: 深度優先 (DFS) 走訪順序

在先前探討 DFS 與 BFS 中，有提及 DFS 的「時間戳記」性質

1. 在 DFS 森林中，如果有 \((u,v)\) 存在，就不會出現 \((v,u)\)，因為每個節點只被拜訪一次
2. 時間戳記中，有一陣列 \(f[i]\) 紀錄節點 \(i\) 完成拜訪所有鄰居的時間
3. 當一節點 \(v\) 完成拜訪，即 \(v\) 的所有在 DFS 森林中的所有後代都已完成拜訪
4. 會發現以完成時間順序由大到小排所有節點 \(v\)，即為拓樸排序

拓樸排序的機制 (Kahn's Algorithm)

首先，這個演算法名稱是這樣唸

說明

step1. 第一個點必不會排在其他點後方，因此要找的 \(v\) 必須 \(deg(v) = 0\)，即入度為 \(0\)
step2. 將每個入度為 \(0\) 的節點走訪過
step3. 刪除每個入度為 \(0\) 的節點，此步驟會產生新的入度為 \(0\) 的節點
step4. 回到 step1. 直到沒有入度為 \(0\) 的節點產生

這想法看起來非常遞迴，實際上用迴圈時做即可，比較看得懂

測環

此方法也可以用於測定是否有環
假設這張有向圖是有環的，則會有可能產生「無法走訪」的節點。因此如果在跑完此演算法之後，發現有節點未被走訪，則這是一張有環有向圖

⭣ 完成拓樸排序後 ⭣

由於沒有任何節點入度為 \(0\)，因此演算法停止，然而仍有三點未被刪去，因此認定此圖有環

拓樸排序的機制 (DFS)

要特別說明一點，要排出順序必須要有「大小關係」

名詞定義

在 DFS 樹或是森林中:

• 白點: 未被走過的節點
• 灰點: 被走過，但並未拜訪完鄰居的節點
• 黑點: 已拜訪完鄰居的節點
• 後向邊: 設 \(u\) 是 \(v\) 的後代，則 \(u\) 連到 \(v\) 的邊為後向邊

引理

對有向圖 \(G\) 進行 DFS 不產生後向邊，若且為若，\(G\) 沒有迴路

定理: 拓樸排序算法能為 \(dag\) 排出優先順序

假設以 DFS 走訪 \(dag\) \(G = (V, E)\)，若有一條邊 \((u, v)\)，則 \(f[u] > f[v]\)，證明如下:

當 \((u,v)\) 邊被發現時

• 如果 \(v\) 是灰點，則 \((u,v)\) 就是一條後向邊，這樣會與引理相違背，因此不可能出現
• 如果 \(v\) 是白點，就代表他是 \(u\) 的後代，因此 \(f[u] > f[v]\)
• 如果 \(v\) 是黑點，則代表此 \((u, v)\) 早已被走訪完畢了，因此 \(f[u] > f[v]\)

得證: 對於 \(G\) 中的所有邊 \((u,v) \in E\) 而言，\(f[u] > f[v]\)
由於每個節點都有「大小關係」，因此可以排出優先順序

測環

根據以上證明，當一條邊 \((u, v)\) 被發現時，如果 \(v\) 是灰點，使 \((u, v)\) 為一條後向邊，則此圖有環

程式實作

刪除節點版本 (Kahn's Algorithm)

在實作上，不需要真的把節點刪除，只需要在走訪節點時將其鄰居的入度 \(-1\) 即可
其實 queue 改成 stack 也會產生一組拓樸排序的結果

C++ code

vector<int> edge[MAXN], ans;  // MAXN: 最大節點數
int deg[MAXN];      // 入度

void topo(int n) {  // 節點編號為 1-based
    queue<int> que; // 以 queue 當作拜訪清單
    
    for (int i = 1; i <= n; i++)
        if (!deg[i]) // 如果入度 == 0 則加入此節點
            que.push(i);
    
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        ans.push_back(u); // 結果存 ans
        
        for (int v : edge[u]) {
            deg[v]--; // 每次走訪完都先幫鄰居的入度 -1
            if (!deg[v]) // 如果入度 == 0 則加入此節點
                que.push(v);
        }
    }
}

時間複雜度

令節點數 \(|V| = n\)、邊數 \(|E| = m\)

• 遍歷整個 \(deg[~]\) : \(O(n)\)
• 遍歷整張圖: \(O(n + m)\)
• 總時間複雜度: \(O(n) + O(n + m) = O(n + m)\)

DFS 版本

C++ code

vector<int> edge[MAXN], ans;
bool vis[MAXN];
int f[MAXN], time_cnt;  // MAXN: 最大節點數

void dfs(int u) {
    vis[u] = true;
    for (int v : edge[u]) {
        if (vis[v])
            continue;
        dfs(v);
    }
    f[u] = ++time_cnt; // 紀錄完成拜訪的時間
    ans.push_back(u); // 將順序存入 ans
}

void topo(int n) {  // 1-base
    time_cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i])
            dfs(i);
    }
    reverse(ans.begin(), ans.end()); // 反轉答案
}

時間複雜度

令節點數 \(|V| = n\)、邊數 \(|E| = m\)

• DFS 整張圖: \(O(n + m)\)
• 將答案存入 \(ans\) : \(O(n)\)
• 反轉 \(ans\) : \(O(n)\)
• 總時間複雜度: \(O(n + m) + O(n) \times 2 = O(n + m)\)

題目練習

Zerojudge f167. m4a1-社團 Club
CSES Course Schedule
UVa 200 - Rare Order
CSES Game Routes
CSES Longest Flight Route (DP on DAG)
AtCoder dp_g - G - Longest Path (DP on DAG)
Zerojudge k734. APCS 4. 開啟寶盒
Codeforces Contest 1385 E. Directing Edges
Zerojudge l245. D. 汽車不再繞圈圈 (二分搜 + 拓排 + 把DFS版本的證明讀熟就會的東西)

---

參考資料

• Introduction to Algorithms, Fourth Edition
• 海大競程 圖論
• geeksforgeeks
• directed acyclic graph - 台師大演算法筆記
• SA 流 C++ 競程修練心法
• Why is "topological sorting" topological?
• Etymology of "topological sorting"

---

ShanC 程式競賽筆記
作者: ShanC
更新: 2024/11/22