课程表

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟡 中等
核心考察点：图、拓扑排序、深度优先搜索 (DFS)、广度优先搜索 (BFS)

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？（即判断图中是否存在环）

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

---

2. 解题思路拆解

这道题本质上是判断一个 有向图 是否存在 环。 如果存在环，则无法完成所有课程；如果不存在环，则可以（这是一个有向无环图 DAG）。

常用的方法是 拓扑排序 (Topological Sort)。

方法一：广度优先搜索 (BFS) - Kahn 算法

1. 入度 (In-degree)：表示有多少门课是当前课程的先修课。
2. 构建图：
   • 使用邻接表 adj 存储图结构（u -> [v1, v2...] 表示学完 u 才能学 v）。
   • 统计每个节点的入度 inDegree。
3. BFS 流程：
   • 将所有 入度为 0 的课程（没有任何先修课，可以直接学）加入队列。
   • 当队列不为空时：
     • 取出队首课程 u。
     • 将已修课程数 count 加 1。
     • 遍历 u 的所有后继课程 v：
       • 将 v 的入度减 1（相当于 u 这门先修课已经搞定了）。
       • 如果 v 的入度变为 0，说明 v 的所有先修课都修完了，可以将 v 加入队列。
4. 结果判断：
   • 如果最终 count 等于 numCourses，说明所有课程都能修完（没有环）。
   • 否则，说明有环（剩下的课程入度都不为 0，互为先修，卡死了）。

方法二：深度优先搜索 (DFS)

DFS 也可以判断环。我们需要三个状态来标记节点：

• 未访问 (0)：还没搜过。
• 访问中 (1)：正在搜该节点的子节点（在当前递归栈中）。
• 已完成 (2)：该节点及其子节点都搜完了，没发现环。

如果在 DFS 过程中遇到了状态为 访问中 (1) 的节点，说明遇到了回边，存在环。

通常 BFS (Kahn 算法) 更直观，也是拓扑排序的标准解法。

---

3. 代码实现 (BFS / Kahn 算法)

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
    // 1. 初始化邻接表和入度数组
    const inDegree = new Array(numCourses).fill(0);
    const adj = new Array(numCourses).fill(0).map(() => []);
    
    // 2. 构建图
    for (const [course, pre] of prerequisites) {
        // pre -> course (想学 course，先学 pre)
        adj[pre].push(course);
        inDegree[course]++;
    }
    
    // 3. 将所有入度为 0 的节点入队
    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (inDegree[i] === 0) {
            queue.push(i);
        }
    }
    
    let count = 0; // 记录已修完的课程数量
    
    // 4. BFS
    while (queue.length > 0) {
        const curr = queue.shift();
        count++;
        
        // 遍历当前课程的所有后续课程
        for (const next of adj[curr]) {
            inDegree[next]--;
            // 如果后续课程的入度变为 0，说明先修课都修完了
            if (inDegree[next] === 0) {
                queue.push(next);
            }
        }
    }
    
    // 5. 判断是否所有课程都修完了
    return count === numCourses;
};

代码执行演示

输入：numCourses = 4, prerequisites = [[1,0], [2,0], [3,1], [3,2]] (0->1, 0->2, 1->3, 2->3)

1. Init:
   • In-degree: [0, 1, 1, 2] (Course 0 has 0, 1 has 1 (from 0), 2 has 1 (from 0), 3 has 2 (from 1,2))
   • Adj: 0->[1,2], 1->[3], 2->[3], 3->[].
   • Queue: [0]
2. BFS:
   • Pop 0. count=1.
     • Neighbors of 0: 1, 2.
     • inDegree[1]-- -> 0. Push 1.
     • inDegree[2]-- -> 0. Push 2.
     • Queue: [1, 2].
   • Pop 1. count=2.
     • Neighbors of 1: 3.
     • inDegree[3]-- -> 1.
     • Queue: [2].
   • Pop 2. count=3.
     • Neighbors of 2: 3.
     • inDegree[3]-- -> 0. Push 3.
     • Queue: [3].
   • Pop 3. count=4.
     • No neighbors.
     • Queue: [].
3. End: count (4) === numCourses (4). Return true.

---

4. 复杂度分析

维度	描述
时间复杂度	$O(V + E)$。$V$ 是课程数，$E$ 是先修关系数。我们需要遍历所有节点和边。
空间复杂度	$O(V + E)$。邻接表存储图需要 $O(V + E)$，入度数组需要 $O(V)$，队列需要 $O(V)$。