LeetCode 207 課程表：拓撲排序判斷有向圖是否有環

問題描述

給定 numCourses 門課程（編號 0 到 n-1）和先修關係 prerequisites（如 [0,1] 表示修 0 需先修 1），判斷是否能完成所有課程。本質是**判斷有向圖是否存在環**。

核心算法：Kahn 算法 (BFS 拓撲排序)

1. 計算每個節點的**入度**（有多少先修課程）。
2. 將所有入度為 0 的節點（無先修課程）加入隊列。
3. 循環：從隊列取出節點 u，計數器++；遍歷 u 的出邊 u→v，將 v 入度--，若變 0 入隊。
4. 若最終計數器 == numCourses，說明無環，可完成；否則有環，不可完成。

關鍵代碼 (Java)

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; ++i) adj.add(new ArrayList<>());
    int[] indegree = new int[numCourses];

    for (int[] pre : prerequisites) {
        adj.get(pre[1]).add(pre[0]); // pre[1] -> pre[0]
        indegree[pre[0]]++;
    }

    Queue q = new LinkedList<>();
    for (int i = 0; i < numCourses; ++i)
        if (indegree[i] == 0) q.offer(i);

    int count = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        count++;
        for (int v : adj.get(u)) {
            if (--indegree[v] == 0) q.offer(v);
        }
    }
    return count == numCourses;
}

複雜度分析

• 時間：O(V + E) — V=課程數，E=先修關係數。
• 空間：O(V + E) — 鄰接表 + 入度陣列 + 隊列。

DFS 環檢測替代方案

用三色標記：0=未訪問，1=訪問中（在遞歸棧中），2=已完成。DFS 過程中若遇到狀態 1 的節點，說明有環。

int[] state = new int[numCourses]; // 0,1,2
boolean hasCycle = false;
function dfs = (u) -> {
    state[u] = 1;
    for (int v : adj.get(u)) {
        if (state[v] == 1) { hasCycle = true; return; }
        if (state[v] == 0) dfs(v);
    }
    state[u] = 2;
};
for (int i = 0; i < numCourses && !hasCycle; ++i)
    if (state[i] == 0) dfs(i);
return !hasCycle;

關鍵點總結

• 圖建模：[a,b] 表示 b → a（b 是 a 的先修）。
• 入度含義：一門課有多少先修課程。
• 拓撲序意義：合法的學習順序。
• 環檢測：無法生成完整拓撲序 ⇔ 有環 ⇔ 無法完成所有課程。

總結

LeetCode 207 是拓撲排序的經典應用。掌握 Kahn 算法（BFS）和 DFS 環檢測兩種模板，可解決所有「任務調度、編譯依賴、課程安排」類問題。BFS 版本更直觀，且易於輸出拓撲序列（見 Course Schedule II）。