Topological Sort拓撲排序

01為什麼需要它

看到這些關鍵字就想到它：相依關係、先後順序、先修課程、A 必須在 B 之前完成、建置／安裝順序、DAG、排程能不能全部完成、有沒有循環相依。

02核心概念

有向圖的拓撲順序是把所有節點排成一列，讓每一條邊 u → v 的 u 都排在 v 前面。它存在的條件恰好是圖為 DAG（有向無環圖），而且通常不只一種。Kahn 演算法的直覺是「誰不用等，誰先做」：入度為 0 的節點沒有任何前置條件，可以排第一；排出去之後刪掉它的出邊，某些節點的入度降到 0，換它們上場。DFS 法從另一頭想：一個節點要等它能走到的節點全部處理完才算完成，把完成順序反轉，就是拓撲順序。

為什麼對：Kahn 只在 indeg[v] 降到 0 時把 v 放進佇列，這時每條指向它的邊 u → v 都已被刪掉，也就是 u 都已輸出，所以每條邊都被遵守。它在 DAG 上不會卡住：非空的 DAG 一定有入度 0 的節點，否則沿著入邊一直往回走，節點有限，終究會走回走過的點，形成環；刪掉節點後剩下的仍是 DAG。反過來，佇列空了卻還有節點沒輸出，剩下的每個節點入度都 ≥ 1，往回走必定繞圈，所以輸出數少於 V 就代表有環，這是 Kahn 附帶的環偵測。DFS 法看任一條邊 u → v：檢查它時 v 若是白色，會在 u 之前遞迴完成；若是黑色，早就完成了；若是灰色（還在呼叫堆疊上），那就是環。所以無環時 v 一定比 u 先完成，反轉後 u 就在 v 前面。

複雜度：Kahn 建入度表掃一次所有邊 O(E)；每個節點進出佇列各一次 O(V)；每條邊只在它的起點被取出時減一次入度 O(E)，合計 O(V+E)。DFS 法每個節點進入一次、每條邊檢查一次，也是 O(V+E)。兩者沒有最好或最壞情況之分，整張圖一定要跑完。額外空間是入度表、佇列、顏色陣列與輸出，都是 O(V)（鄰接串列本身的 O(V+E) 算在輸入裡）。DFS 的遞迴深度最壞是 V（一條長鏈），Python 預設遞迴上限只有 1000，節點多時改用 Kahn。

最常見的錯是邊的方向接反：LeetCode 207、210 的 [a, b] 表示「修 a 之前要先修 b」，邊是 b → a。DFS 法常忘了反轉完成順序，或只用一個 visited 布林值、不區分灰色，結果圖裡有環也照樣輸出一個錯的順序；外層迴圈也要對每個節點都試，因為圖不一定連通。和相鄰課程的關係：Kahn 的佇列走法就是 BFS 的骨架，DFS 法是 DFS 的後序，三色標記和 Cycle Detection 完全相同，拓撲排序等於「做環偵測時順便記下順序」。要字典序最小的順序，把佇列換成最小堆積，時間變成 O(V log V + E)；要知道最少分幾輪平行做完，就讓 Kahn 一次處理一整層。有了拓撲順序，照順序鬆弛每條邊就能在 DAG 上求最短路徑，那是 DAG Shortest Path 的做法。

03演算法步驟

1. 1把每條相依寫成邊：「u 必須在 v 之前」就加 u → v，同時 indeg[v] += 1。先確認題目給的 pair 是哪個方向。
2. 2把所有入度為 0 的節點放進佇列，它們沒有任何前置條件。
3. 3從佇列取出 u 加到答案；對 u 的每條出邊 u → v 做 indeg[v] -= 1，降到 0 就把 v 放進佇列。
4. 4佇列空了就停。答案長度等於 V 就是拓撲順序；少於 V 代表有環，入度還大於 0 的節點都卡在環上或環的下游。
5. 5DFS 寫法：三色標記，外層迴圈對每個白色節點呼叫 dfs；碰到灰色鄰居就是環；一個節點的鄰居全部處理完才把它加入 post，最後回傳 post 反轉。
6. 6變形：要分批平行處理，就一次把整層取完再算下一層，層數是最少輪數；要字典序最小，把佇列換成最小堆積。

04互動示範

6 個前端套件、8 條相依，箭頭 u → v 表示裝 v 之前要先裝 u。「Kahn · 入度」模式看節點下方的 in=：每移除一條邊（變成虛線）就減 1，降到 0 的套件變黃色進佇列，藍色是正在處理的，填滿的是已輸出。「DFS · 完成順序」模式裡黃色是還在呼叫堆疊上的套件，節點下方標出它是第幾個完成，右欄同時列出完成順序與它的反轉。留意兩個模式的結果：Kahn 得到 react → ts → r-dom → lint → next → app，DFS 得到 ts → lint → react → r-dom → next → app，順序不同，但每條相依都成立。

05程式碼

兩種語言都有 Kahn 與 DFS 兩種寫法，範例圖和互動示範相同，輸出也分別對應兩個模式的結果。Kahn 不用遞迴、順便數出有沒有環，是實務上的預設選擇；DFS 版和環偵測共用三色標記，適合已經在做 DFS 的場合。Python 另外示範分層版本，每一層可以平行處理；C++ 示範把佇列換成最小堆積，得到字典序最小的順序。

from collections import deque


def topo_kahn(n, edges):
    """Kahn：反覆取出入度為 0 的節點。有環時回傳 []。O(V+E)"""
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:                  # u → v：u 必須排在 v 前面
        adj[u].append(v)
        indeg[v] += 1
    queue = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1               # 移除邊 u → v
            if indeg[v] == 0:           # v 的前置條件全部排好了
                queue.append(v)
    return order if len(order) == n else []   # 少於 n 個代表有環


def topo_dfs(n, edges):
    """DFS：三色標記，完成順序反轉。O(V+E)"""
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    post = []

    def dfs(u):
        color[u] = GRAY                 # 在呼叫堆疊上
        for v in adj[u]:
            if color[v] == GRAY:        # 回邊：有環
                return False
            if color[v] == WHITE and not dfs(v):
                return False
        color[u] = BLACK
        post.append(u)                  # u 能走到的節點都完成了，才輪到 u
        return True

    for i in range(n):                  # 圖不一定連通，每個起點都要試
        if color[i] == WHITE and not dfs(i):
            return []
    return post[::-1]


def topo_layers(n, edges):
    """Kahn 分層：同一層彼此沒有相依，可以平行處理"""
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    layer = [i for i in range(n) if indeg[i] == 0]
    layers, count = [], 0
    while layer:
        layers.append(layer)
        count += len(layer)
        nxt = []
        for u in layer:                 # 整層一起取出，再算下一層
            for v in adj[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    nxt.append(v)
        layer = nxt
    return layers if count == n else []


if __name__ == "__main__":
    # 和互動示範同一張圖：0 react、1 ts、2 r-dom、3 lint、4 next、5 app
    edges = [(0, 2), (0, 4), (2, 4), (2, 5), (1, 3), (1, 4), (4, 5), (3, 5)]
    print(topo_kahn(6, edges))                    # [0, 1, 2, 3, 4, 5]
    print(topo_dfs(6, edges))                     # [1, 3, 0, 2, 4, 5]
    print(topo_layers(6, edges))                  # [[0, 1], [2, 3], [4], [5]]
    print(topo_kahn(3, [(0, 1), (1, 2), (2, 0)])) # []（有環）

06練習題

• LeetCode 1557Minimum Number of Vertices to Reach All Nodes（入度為 0 的節點）Medium
• LeetCode 210Course Schedule II（注意邊的方向）Medium
• LeetCode 2115Find All Possible Recipes from Given Supplies（字串節點的 Kahn）Medium
• LeetCode 802Find Eventual Safe States（反向圖做 Kahn，或三色 DFS）Medium
• LeetCode 2050Parallel Courses III（拓撲順序上算最早完成時間）Hard
• LeetCode 1203Sort Items by Groups Respecting Dependencies（兩層拓撲排序）Hard