跳至主要内容

Topological Sort

預備知識

拓撲排序（Topological Sort）指的是：針對一個有向無環圖（DAG, Directed Acyclic Graph），把所有節點排成一列，使得每一條邊 u → v，在排列結果中 u 都一定出現在 v 前面。

白話理解

最經典的例子是大學選課：如果修「資料結構」之前必須先修過「程式設計」，那麼在你的修課計畫（排列順序）裡，「程式設計」就一定要排在「資料結構」前面。拓撲排序做的事，就是幫你把所有課程排出一個「不會違反先修規定」的合法順序。

其他常見的生活例子還有：早上穿衣服（內衣要先於外套）、做菜食譜的步驟依賴、專案任務排程（某些工作必須等前置工作完成才能開始）。

使用限制

拓撲排序只能用在有向無環圖（DAG）上。如果圖裡面有「環（Cycle）」，代表存在互相依賴、永遠無法決定先後順序的情況（例如「修 A 前要先修 B，但修 B 前又要先修 A」），這時候拓撲排序無解。

做法一：Kahn's Algorithm（BFS 為基礎）​

核心概念是 「入度（In-degree）」：一個節點的入度，代表有幾條邊指向它，也就是「還有幾個前置條件沒完成」。

步驟​

  1. 計算每個節點的入度（有幾個前置條件）。
  2. 把所有「入度為 0」的節點（沒有任何前置條件）放進 Queue。
  3. 從 Queue 取出一個節點，加入排序結果，並把它所有鄰居的入度都減 1（代表這個前置條件已經完成）。
  4. 如果某個鄰居的入度因此變成 0，代表它的前置條件都完成了，放入 Queue。
  5. 重複步驟 3、4，直到 Queue 淨空。
from collections import deque

def topological_sort(num_nodes, edges):
    adjacency_list = [[] for _ in range(num_nodes)]
    in_degree = [0] * num_nodes

    # 建立 Graph，並統計每個節點的入度
    for from_node, to_node in edges:
        adjacency_list[from_node].append(to_node)
        in_degree[to_node] += 1

    # 把所有目前沒有前置條件的節點放進 queue
    queue = deque(i for i in range(num_nodes) if in_degree[i] == 0)

    result = []
    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in adjacency_list[node]:
            in_degree[neighbor] -= 1  # 這個前置條件已經完成，鄰居的入度減 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)  # 鄰居的前置條件都做完了，可以排進去了

    # 如果排序結果的節點數，比原本的節點總數還少，代表圖裡面有環
    if len(result) != num_nodes:
        return []  # 或依需求拋出錯誤

    return result

逐步拆解：課程先修關係​

假設有 4 門課（用 0, 1, 2, 3 代表），先修規則是 [1, 0]、[2, 0]、[3, 1]、[3, 2]（[a, b] 代表要修 a 必須先修 b，也就是邊是 b → a）：

0 → 1 → 3
0 → 2 → 3
步驟Queue（待排入的節點）排序結果說明
初始化[0]（只有 0 的入度是 0）[]課程 1、2 都要先修 0；課程 3 要先修 1 和 2
1[1, 2][0]取出 0，把 1、2 的入度各減 1，兩者都變成 0，放進 Queue
2[2][0, 1]取出 1，把 3 的入度減 1（3 還在等 2 完成，入度變成 1，還不能放入）
3[3][0, 1, 2]取出 2，把 3 的入度再減 1，變成 0，放進 Queue
4[][0, 1, 2, 3]取出 3，Queue 淨空，排序完成

最終合法的修課順序是：0 → 1 → 2 → 3（或 0 → 2 → 1 → 3 也同樣合法，拓撲排序的結果通常不只一種）。

做法二：DFS 為基礎​

另一種做法是利用 DFS，對每個節點做 PostOrder（先拜訪完所有鄰居，才把自己加進結果），最後把整個結果反過來，就是合法的拓撲排序。

def topological_sort_dfs(num_nodes, edges):
    adjacency_list = [[] for _ in range(num_nodes)]
    for from_node, to_node in edges:
        adjacency_list[from_node].append(to_node)

    visited = set()
    result = []

    def dfs(node):
        visited.add(node)
        for neighbor in adjacency_list[node]:
            if neighbor not in visited:
                dfs(neighbor)
        result.append(node)  # 所有鄰居都拜訪完了，才輪到自己

    for i in range(num_nodes):
        if i not in visited:
            dfs(i)

    result.reverse()  # 別忘了反過來！
    return result
新手小提醒

DFS 版本容易忘記最後要 reverse()。因為 DFS 是「越晚被完全處理完的節點，越應該排在越前面」，所以收集到的順序其實是相反的，一定要反轉回來才是正確答案。

複雜度​

  • 時間複雜度：O(V + E)，每個節點與每條邊都只會被處理一次。
  • 空間複雜度：O(V + E)，需要儲存 Graph、入度陣列（或 visited 集合）與結果陣列。

適用情況​

  • 課程 / 任務排程：安排有先後依賴關係的任務執行順序。
  • 建置工具的相依關係解析：例如 npm/yarn 安裝套件、Webpack 打包模組時，需要先確定哪些模組要先被處理。
  • 試算表公式計算順序：如果 B 儲存格的公式參照了 A 儲存格，A 就必須先算完。
  • 偵測循環依賴（Circular Dependency）：如果排序結果的節點數量比總節點數少，代表圖中存在環，這也是拓撲排序常被拿來做「環偵測」的原因。

常見誤區​

  • 忘記先檢查圖中是否有環：如果圖裡有環，Kahn's Algorithm 最後 Queue 會提早淨空，導致排序結果的節點數量少於總節點數，這時候要記得判斷並回報「無解」，而不是直接回傳不完整的結果。
  • 誤以為拓撲排序的結果是唯一的：只要不違反邊的方向限制，通常存在多種合法排序，題目如果要求「唯一解」，通常還會加上其他排序條件（例如優先處理編號較小的節點）。
  • DFS 版本忘記反轉結果：如上方提醒，DFS-based 做法收集到的順序是相反的，忘記 reverse() 會得到完全顛倒的錯誤答案。
  • 搞混入度與出度：入度（In-degree）是「有幾條邊指向自己」，代表還剩幾個前置條件；出度（Out-degree）是「自己指向幾條邊」，兩者容易搞混，Kahn's Algorithm 用的是入度。
最後於 更新