拓樸排序教學：原理、程式碼與時間複雜度

拓樸排序解決什麼問題

許多實際任務都有先決條件：一門課需要先修其他課程、原始檔必須在它引入的檔案之後編譯、套件必須在其相依套件之後安裝、試算表的儲存格必須在它參照的儲存格之後計算。把每個任務畫成節點，把每條「必須先於」的規則畫成有向邊，拓樸順序就是符合所有邊的任務序列。

順序存在，若且唯若圖中沒有有向環。如果 A 需要 B、B 又需要 A，就不存在合法的順序，而好的拓樸排序會回報這一點，而不是無窮迴圈。DAG 通常有許多合法順序；演算法只會回傳其中一個。

用白話說明原理

Kahn 演算法（Arthur Kahn 於 1962 年發表）從前面開始處理：

1. 計算每個節點的入邊數（入度）。
2. 把所有入度為 0 的節點放進佇列：這些任務沒有尚未滿足的先決條件。
3. 從佇列取出一個節點，附加到結果中。對它的每條外向邊，把目標節點的入度減 1；如果降到 0，就把目標加入佇列。
4. 佇列清空後，如果結果包含所有節點，它就是一個拓樸順序；否則剩下的節點屬於某個環。

DFS 方法則從後面開始處理：一個節點必須等它指向的所有節點都完成後才算完成，所以把節點依完成時間反向列出，就能讓每個節點排在所有後繼節點之前。

逐步範例

穿衣服：內褲 → 長褲、長褲 → 鞋子、襪子 → 鞋子、長褲 → 皮帶、襯衫 → 皮帶、襯衫 → 領帶、領帶 → 外套、皮帶 → 外套。以下是 Kahn 演算法依先進先出順序處理佇列節點的過程：

最終順序：內褲、襪子、襯衫、長褲、領帶、鞋子、皮帶、外套。全部 8 個節點都已排入，所以沒有環。

Python 實作

使用 deque 的 Kahn 演算法：

from collections import deque
def topo_sort(graph):
    """graph: dict node -> list of nodes that must come after it."""
    indegree = {n: 0 for n in graph}
    for n in graph:
        for m in graph[n]:
            indegree[m] += 1
    queue = deque(n for n in graph if indegree[n] == 0)
    order = []
    while queue:
        n = queue.popleft()
        order.append(n)
        for m in graph[n]:
            indegree[m] -= 1
            if indegree[m] == 0:
                queue.append(m)
    if len(order) != len(graph):
        raise ValueError("graph has a cycle")
    return order
dress = {
    "underwear": ["pants"], "socks": ["shoes"], "shirt": ["belt", "tie"],
    "pants": ["shoes", "belt"], "tie": ["jacket"], "belt": ["jacket"],
    "shoes": [], "jacket": [],
}
print(topo_sort(dress))
# ['underwear', 'socks', 'shirt', 'pants', 'tie', 'shoes', 'belt', 'jacket']

DFS 版本在節點的所有後繼都完成後才附加該節點，最後再反轉串列：

def topo_sort_dfs(graph):
    order, state = [], {}             # state: 1 = in progress, 2 = done
    def visit(n):
        if state.get(n) == 1:
            raise ValueError("graph has a cycle")
        if state.get(n) == 2:
            return
        state[n] = 1
        for m in graph[n]:
            visit(m)
        state[n] = 2
        order.append(n)
    for n in graph:
        visit(n)
    return order[::-1]
print(topo_sort_dfs(dress))
# ['shirt', 'tie', 'socks', 'underwear', 'pants', 'belt', 'jacket', 'shoes']

兩種輸出都是合法的。從 Python 3.9 起，標準函式庫也提供 graphlib.TopologicalSorter。請注意，它接受的是從每個節點對應到其前驅節點的映射，與上面字典的方向相反：

from graphlib import TopologicalSorter
ts = TopologicalSorter({"b": {"a"}, "c": {"a", "b"}})   # node: its prerequisites
print(list(ts.static_order()))  # ['a', 'b', 'c']

時間與空間複雜度

變化版本與常見錯誤

• 最小順序優先：把佇列換成最小堆積（heapq），每次都挑出可用節點中最小的，即可在 O((V + E) log V) 內得到字典序最小的順序。
• 平行排程：以「輪」為單位執行 Kahn 演算法，每輪一次取出所有入度為 0 的節點。每一輪就是一批可以同時執行的任務，輪數即為最長相依鏈的長度。graphlib.TopologicalSorter 以 get_ready() 和 done() 支援這種用法。
• DAG 中的最長或最短路徑：依拓樸順序鬆弛各條邊，即使有負權重，也能在 O(V + E) 內得到答案。
• 計算不同順序的數量是困難得多的問題；對大型圖，請不要嘗試列出全部順序。

遞迴 DFS 版本和 Python 中任何遞迴 DFS 一樣有遞迴深度限制：如果鏈上有數千個節點，請改用 Kahn 演算法。

何時使用與實際應用

• Make 等建置工具依相依關係排列目標，套件管理工具依相依圖排列安裝順序。
• 試算表依相依順序重新計算儲存格，並回報循環參照。
• 任務排程器與工作流程引擎（例如以 DAG 為基礎的資料管線）依拓樸順序執行任務。
• 編譯器排列宣告順序並計算運算式圖；資料庫排列外部鍵的建立或刪除順序。
• 面試題目：課程表 I 與 II、外星字典（由排序後的單字推得字母順序）、平行課程、建置計畫的最小高度。