拓撲排序#

什麼是拓撲排序？#

將有向無環圖 (DAG) 的頂點排成線性序列，使得所有邊 (u, v) 中，u 都排在 v 之前。

生活範例：穿衣順序#

flowchart LR
    內褲 --> 外褲
    外褲 --> 腰帶
    上衣 --> 腰帶
    腰帶 --> 外套
    襪子 --> 鞋子

    style 內褲 fill:#e3f2fd
    style 襪子 fill:#e3f2fd
    style 上衣 fill:#e3f2fd
    style 外套 fill:#e8f5e9
    style 鞋子 fill:#e8f5e9

有效的拓撲序列：內褲 → 襪子 → 上衣 → 外褲 → 鞋子 → 腰帶 → 外套

拓撲排序的結果不唯一，只要滿足所有依賴關係即可。

應用場景#

編譯依賴：確定源檔案的編譯順序
課程先修：安排課程學習順序
任務調度：確定任務執行順序
環檢測：判斷有向圖是否有環

Kahn 演算法（BFS）#

核心思想#

不斷找出入分支度為 0 的頂點（無依賴），輸出並移除。

演算法步驟#

flowchart TD
    A[1. 計算所有頂點入分支度] --> B[2. 入分支度=0 的頂點入隊]
    B --> C{佇列為空?}
    C -->|否| D[3. 取出頂點並輸出]
    D --> E[4. 相鄰頂點入分支度 -1]
    E --> F{入分支度變為 0?}
    F -->|是| G[加入佇列]
    F -->|否| C
    G --> C
    C -->|是| H{輸出數 = 頂點數?}
    H -->|是| I[拓撲排序完成]
    H -->|否| J[存在環！]

    style I fill:#e8f5e9
    style J fill:#ffebee

計算所有頂點的入分支度
將入分支度為 0 的頂點加入佇列
取出佇列頂點，輸出，將其相鄰頂點入分支度 -1
若有新的入分支度為 0 的頂點，加入佇列
重複直到佇列為空

Kahn 演算法程式碼

from collections import deque

def topological_sort_kahn(n, edges):
    # 建圖 + 計算入分支度
    graph = [[] for _ in range(n)]
    in_degree = [0] * n

    for u, v in edges:  # u → v
        graph[u].append(v)
        in_degree[v] += 1

    # 入分支度為 0 的頂點入隊
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = []

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

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # 檢測環：若輸出數量不等於頂點數，說明有環
    return result if len(result) == n else []

DFS 演算法#

核心思想#

後序走訪的逆序即為拓撲排序。

演算法步驟#

對每個未訪問的頂點執行 DFS
遞迴訪問所有依賴的頂點
回溯時將當前頂點加入結果（後序）
最後反轉結果

DFS 演算法程式碼

def topological_sort_dfs(n, edges):
    # 建立逆鄰接串列（指向依賴的頂點）
    graph = [[] for _ in range(n)]
    for u, v in edges:  # u → v（v 依賴 u）
        graph[v].append(u)  # 逆向：v 需要先完成 u

    visited = [False] * n
    result = []

    def dfs(node):
        if visited[node]:
            return
        visited[node] = True

        for dep in graph[node]:
            dfs(dep)

        result.append(node)  # 後序：依賴都處理完才輸出自己

    for i in range(n):
        dfs(i)

    return result  # 已經是正確順序（使用逆鄰接串列）

複雜度分析#

演算法	時間複雜度	空間複雜度
Kahn	O(V + E)	O(V)
DFS	O(V + E)	O(V)

環檢測#

有環 = 無法拓撲排序

Kahn 演算法檢測#

若最終輸出的頂點數 < 總頂點數，說明有環。

DFS 檢測#

維護三種狀態：未訪問、訪問中、已完成

若訪問到「訪問中」的頂點，說明有環

def has_cycle(n, edges):
    UNVISITED, VISITING, VISITED = 0, 1, 2
    state = [UNVISITED] * n
    graph = [[] for _ in range(n)]

    for u, v in edges:
        graph[u].append(v)

    def dfs(node):
        if state[node] == VISITING:
            return True  # 發現環
        if state[node] == VISITED:
            return False

        state[node] = VISITING
        for neighbor in graph[node]:
            if dfs(neighbor):
                return True
        state[node] = VISITED
        return False

    return any(dfs(i) for i in range(n) if state[i] == UNVISITED)