拓樸排序 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