題目
#

leetcode 207 - Course Schedule (題目說明請點連結)

題目簡述
#

給定一個課程數量和它們的先修課程，判斷是否可以完成所有課程。

範例
#

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: 總共有 2 門課程。要學習課程 1，你需要先完成課程 0。所以這是可能的。

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: 總共有 2 門課程。要學習課程 1，你需要先完成課程 0，並且要學習課程 0，你需要先完成課程 1。這是不可能的。

Example 3:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: true
Explanation: 總共有 4 門課程。要學習課程 3，你應該先完成課程 1 和 2，並且課程 1 和 2 都應該排在課程 0 之後。所以一個正確的課程順序是 [0,1,2,3]。

解題思路
#

這題要求我們判斷是否可能完成所有課程的學習。本質上是在判斷一個有向圖是否存在環。如果存在環，說明課程之間存在循環依賴，無法完成所有課程；如果不存在環，說明可以找到一個合法的學習順序。

解題方法
#

有兩種主要的解題方法：

BFS：通過拓撲排序檢測環
DFS：通過 DFS 檢測環

BFS
#

解法
#

拓撲排序（Topological Sorting）

使用 adjacency list 構建有向圖，其中 prerequisites[i] = [ai, bi] 表示 bi -> ai 的邊
計算每個節點的 in-degree
將所有入度為 0的節點加入 queue
從 queue 中取出節點，將其所有相鄰節點的in-degree 減 1
如果某個節點的in-degree 變為 0，將其加入 queue
重複步驟 4-5，直到 queue 為空
如果訪問的節點數量等於總節點數量，說明沒有環，返回 true

例子說明
#

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

graph TD; A[0] B[1] C[2] D[3] A --> B A --> C B --> D C --> D

構建圖：0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3
計算入度：indegree[0] = 0, indegree[1] = 1, indegree[2] = 1, indegree[3] = 2

步驟	當前節點	入度更新	佇列狀態	已訪問節點	說明
初始	-	-	`[0]`	`[0]`	節點 0 入度為 0
第 1 步	0	`indegree[1]=0`, `indegree[2]=0`	`[1,2]`	`[0,1,2]`	處理節點 0
第 2 步	1	`indegree[3]=1`	`[2]`	`[0,1,2]`	處理節點 1
第 3 步	2	`indegree[3]=0`	`[3]`	`[0,1,2,3]`	處理節點 2
第 4 步	3	-	`[]`	`[0,1,2,3]`	處理節點 3

最終結果：

訪問的節點數量 = 4，等於總節點數量
返回 true

BFS 完整程式碼
#

java

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 構建 adjacency list 表示的圖
        List<List<Integer>> graph = new ArrayList<>();
        int[] indegree = new int[numCourses];

        // 初始化圖
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 添加 edges 並計算 in-degree
        for (int[] pre : prerequisites) {
            graph.get(pre[1]).add(pre[0]);
            indegree[pre[0]]++;
        }

        // 將所有 in-degree 為 0 的 nodes 加入 queue
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) queue.add(i);
        }

        int count = 0; // 已訪問的 node 數量
        
        // BFS 處理
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            count++;
            
            // 將當前 node 的所有 adjacent nodes 的 in-degree 減 1
            for (int next : graph.get(cur)) {
                indegree[next]--;
                if (indegree[next] == 0) queue.add(next);
            }
        }

        // 如果訪問的 node 數量等於總 node 數量，說明沒有 cycle
        return count == numCourses;
    }
}

DFS
#

解法
#

使用 adjacency list 構建有向圖
維護一個 visited 狀態陣列：
- visited[i] = 0：未訪問（unvisited）
- visited[i] = 1：正在訪問（visiting，在 DFS 遞迴中）
- visited[i] = 2：已完成訪問（visited）
對每個節點進行 DFS 遍歷
如果在 DFS 過程中遇到狀態為 1 的節點，說明存在環

例子說明
#

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

構建圖：0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3

步驟	當前節點	狀態變化	操作	結果
第 1 步	0	`visited[0] = 1`	遞迴訪問節點 1	繼續
第 2 步	1	`visited[1] = 1`	遞迴訪問節點 3	繼續
第 3 步	3	`visited[3] = 1` → `visited[3] = 2`	無相鄰節點，完成	返回 true
第 4 步	1	`visited[1] = 2`	完成訪問	返回 true
第 5 步	0	遞迴訪問節點 2	`visited[2] = 1`	繼續
第 6 步	2	訪問節點 3（已訪問）	`visited[2] = 2`	返回 true
第 7 步	0	`visited[0] = 2`	完成訪問	返回 true

最終結果：

所有節點都成功完成 DFS，沒有發現環
返回 true

DFS 完整程式碼
#

java

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 構建 adjacency list 表示的圖
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 添加 edge：prerequisites[i] = [ai, bi] 表示 bi -> ai
        for (int[] pre : prerequisites) {
            graph.get(pre[1]).add(pre[0]);
        }

        // visited 狀態陣列：0=未訪問, 1=訪問中, 2=已完成
        int[] visited = new int[numCourses];

        // 對每個 node 進行 DFS
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(graph, visited, i)) return false;
        }
        return true;
    }

    private boolean dfs(List<List<Integer>> graph, int[] visited, int course) {
        if (visited[course] == 1) return false; // 發現環
        if (visited[course] == 2) return true;  // 已完成

        visited[course] = 1; // 標記正在訪問
        
        // 遞迴訪問所有 adjacent nodes
        for (int next : graph.get(course)) {
            if (!dfs(graph, visited, next)) return false;
        }
        
        visited[course] = 2; // 標記已完成
        return true;
    }
}