LeetCode 刷題日記
EP.14

EP.14 — Graph 進階：
拓撲排序與環的偵測

#207 Course Schedule · #210 Course Schedule II
— Kahn's Algorithm、DFS Cycle Detection、有向圖的排序問題

Joseph Chen

2024
5 min read
1.2k views

EP.13 學了 Graph DFS 的基礎：visited 集合防環、Grid 與 Adjacency List 兩種形式。這篇進入「有向圖」的核心問題：

「這些任務能不能被排出一個合法的完成順序？」

如果任務之間存在循環依賴（A 需要 B 先完成，B 需要 A 先完成），就無解。這就是拓撲排序（Topological Sort）要解決的問題，也是面試最常考的 Graph 進階題。

前置概念：In-degree（入度）

有向圖中，一個節點的「入度」是指有多少條邊指向它。 入度為 0 的節點代表「沒有任何前置條件」，可以最先被處理。

例：修課依賴圖

數學
in=0
→
線性代數
in=1
→
機器學習
in=2
統計學
in=0
──────────────────────→

「機器學習」有兩條前置（線性代數＋統計學），所以入度 = 2。 要學機器學習，必須先把入度降到 0。

📚

Part 1 — Course Schedule

#207 · Medium · 能否完成所有課程？

題目

有 numCourses 門課，prerequisites[i] = [a, b] 代表「修 a 之前必須先修 b」。 判斷是否能完成所有課程（即依賴關係中是否存在環）。

numCourses=2, prerequisites=[[1,0]] → True（先修0再修1）

numCourses=2, prerequisites=[[1,0],[0,1]] → False（互相依賴，有環）

解法一：Kahn's Algorithm（BFS 拓撲排序）

核心思路：每次從圖中移除入度為 0 的節點，直到圖為空（成功）或卡住（有環）。

Kahn's 演算法步驟

1

建圖 + 計算每個節點的 in-degree

graph[b].append(a)  # b → a（修b才能修a）
2

把所有 in-degree=0 的節點加入 queue

queue = deque([i for i in range(n) if indegree[i] == 0])
3

BFS：處理節點，更新鄰居 in-degree

# 每移除一個節點，其鄰居的 in-degree -= 1
# 若鄰居 in-degree 變 0，加入 queue
4

最後檢查：處理的節點數是否等於 numCourses

# 如果有環，環裡的節點永遠 in-degree > 0，不會被處理
course_schedule_bfs.py
from collections import deque, defaultdict

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = defaultdict(list)
    indegree = [0] * numCourses

    for a, b in prerequisites:
        graph[b].append(a)   # b → a（修完 b 才能修 a）
        indegree[a] += 1

    # 入度為 0 的課程可以先修
    queue = deque([i for i in range(numCourses) if indegree[i] == 0])
    finished = 0

    while queue:
        course = queue.popleft()
        finished += 1
        for next_course in graph[course]:
            indegree[next_course] -= 1
            if indegree[next_course] == 0:
                queue.append(next_course)

    return finished == numCourses  # 所有課都處理到才代表無環
⏱ Time: O(V + E)💾 Space: O(V + E)

Kahn's 演算法可視化

prerequisites = [[1,0],[2,1],[3,1]]

初始
0
in=0
→
1
in=1
→
2
in=1
也→
3
in=1
移除 0
0
done
→
1
in=0
→
2
in=1
→
3
in=1
移除 1
0
done
1
done
2
in=0
3
in=0
完成finished=4 == numCourses → True ✅

解法二：DFS 環偵測（三色標記法）

另一種思路：用 DFS 遍歷圖，用三種狀態標記每個節點——未訪問、正在訪問中（在當前 DFS 路徑上）、已完成。如果遇到「正在訪問中」的節點，代表有環。

course_schedule_dfs.py
def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = defaultdict(list)
    for a, b in prerequisites:
        graph[b].append(a)

    # 0 = 未訪問, 1 = 正在訪問中（當前路徑上）, 2 = 已完成（安全）
    state = [0] * numCourses

    def dfs(node) -> bool:
        if state[node] == 1:   # 在當前路徑上再次遇到 → 有環
            return False
        if state[node] == 2:   # 已確認安全，不用再訪
            return True

        state[node] = 1        # 標記為「正在訪問」
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        state[node] = 2        # DFS 完成，標記為「安全」
        return True

    return all(dfs(i) for i in range(numCourses))
⏱ Time: O(V + E)💾 Space: O(V + E)

Kahn's（BFS）適合用在

  • • 需要輸出排序結果（Course Schedule II）
  • • 邏輯直觀，容易理解
  • • 不需要遞迴，無 stack overflow 風險

DFS 三色標記適合用在

  • • 只判斷有無環，不需要排序
  • • 面試偏好 DFS 的考官
  • • 邏輯上更貼近「回溯路徑」的直覺
📋

Part 2 — Course Schedule II

#210 · Medium · 輸出拓撲排序結果

和 #207 幾乎一樣，差別在於不只要回傳「能否完成」，還要回傳「一個合法的修課順序」。如果有環則回傳空陣列。

用 Kahn's Algorithm 的話，只要把 queue.popleft() 的節點順序收集起來就是答案。

course_schedule_ii.py
from collections import deque, defaultdict

def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    graph = defaultdict(list)
    indegree = [0] * numCourses

    for a, b in prerequisites:
        graph[b].append(a)
        indegree[a] += 1

    queue = deque([i for i in range(numCourses) if indegree[i] == 0])
    order = []

    while queue:
        course = queue.popleft()
        order.append(course)          # 收集處理順序
        for next_course in graph[course]:
            indegree[next_course] -= 1
            if indegree[next_course] == 0:
                queue.append(next_course)

    return order if len(order) == numCourses else []  # 有環則回傳 []
⏱ Time: O(V + E)💾 Space: O(V + E)

拓撲排序通用模板

遇到「有依賴關係的任務排序」或「判斷是否有循環依賴」，直接套這個框架：

topological_sort_template.py
from collections import deque, defaultdict

def topological_sort(n: int, edges: list[tuple]) -> list[int]:
    graph = defaultdict(list)
    indegree = [0] * n

    for src, dst in edges:           # src → dst（src 是 dst 的前置）
        graph[src].append(dst)
        indegree[dst] += 1

    queue = deque([i for i in range(n) if indegree[i] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return result if len(result) == n else []  # [] 代表有環

模板要注意的地方

• 邊的方向：要確認 graph 中 edge 的方向。Course Schedule 裡 [a, b] 代表「先修 b 才能修 a」，所以要建 b → a 的邊。

• in-degree 初始化：必須先遍歷所有邊，才能正確算出每個節點的入度。

• 結果長度判斷：len(result) == n 是唯一正確的有環判斷方式，不要另外另 check。

Graph 兩篇總結

題目Graph 類型核心技術關鍵資料結構
Number of Islands無向 GridDFS / BFS 淹島set / 直接改值
Clone Graph無向圖DFS + HashMap 防環dict{old: new}
Course Schedule有向圖（DAG 判斷）Kahn's / DFS 三色indegree[], deque
Course Schedule II有向圖（拓撲排序）Kahn's，收集順序indegree[], deque, result[]

這篇學到什麼

📚Course Schedule 本質是「有向圖有無環」，有環代表有循環依賴，無法完成
🔢Kahn's Algorithm：每次移除入度為 0 的節點，最後看處理數量是否等於總節點數
🎨DFS 三色標記：未訪問(0) → 訪問中(1) → 已完成(2)，遇到狀態 1 代表有環
📋Course Schedule II 只是在 Kahn's 基礎上多收集一個 order 陣列
⚠️有向圖必須注意邊的方向，[a, b] 代表「先修 b 再修 a」，建圖方向別搞反

上一篇

EP.13 — Graph 入門

Number of Islands、Clone Graph

下一篇

EP.15 — Backtracking

Subsets、Permutations、Combination Sum

LeetCode
Graph
Topological Sort
BFS
Python
EP.14