题型地图 56天全屏 141题

当前：LC207 · 课程表 · 首次出现于 Day 31 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

80 / 141回到 Day 31 卡片 141 题索引

LC207

LC207 课程表：这些课能不能全部修完？

把课程前置关系转换成一张有向图，再用“课程调度器”一门门解锁。

先用人话看懂题目，再把每个 [a,b]翻译成前置课程 → 后续课程，最后观察课程如何被一门门解锁。

课程调度实验室题意先行前置锁queue 传送带

read first

题意重述

你有 numCourses 门课，编号从 0 到 numCourses - 1。

prerequisites[i] = [a, b] 表示：想修课程 a，必须先修课程 b。

问题是：按照这些前置关系，能不能把所有课程都修完？

有些课程必须先修别的课程。我们要判断：这些课程依赖关系里，有没有互相等待的死循环。如果没有环，就能修完；如果有环，就修不完。

先别急着看代码

这页先把“课程等待关系”讲清楚，再把关系画成图，最后才解释入度、queue 和 BFS 拓扑排序。

one example

统一主例：4 门课怎么被一门门解锁

const example = {
numCourses: 4,
prerequisites: [[1,0], [2,0], [3,1], [3,2]],
}

[1,0]：修 1 之前，要先修 0

[2,0]：修 2 之前，要先修 0

[3,1]：修 3 之前，要先修 1

[3,2]：修 3 之前，要先修 2

最终直觉

0先修 0

再修 1 和 2

最后修 3

所以可以修完。

为什么要用图？

因为课程之间不是简单的一条线，而是一组“谁必须在谁之前完成”的关系。这种关系最适合用图表达：课程 = 顶点，前置依赖 = 有向边。

[a,b] 为什么是 b → a？

[a,b] 表示：修 a 之前，必须先修 b。所以边的方向是 b → a。这条边的含义是：学完 b 后，a 才可能被解锁。

indegree 到底是什么？

indegree[i] 表示课程 i 还欠几门前置课。indegree[i] = 0，说明这门课现在就能修。

queue 里放什么？

queue 里只放当前可以修的课程。每修完一门课，就尝试解锁它后面的课程。

为什么 learned == numCourses 就说明可以修完？

如果所有课程都被修过，说明没有课程被卡住。如果 queue 空了，但 learned 还小于 numCourses，说明剩下的课程互相等待，形成了环。

有环反例放在正例之后

反例使用 prerequisites = [[0,1],[1,2],[2,0]]，形成 1 → 0 → 2 → 1。没有任何一门课入度为 0，没有起点，所有课程都在等另一门课先完成，这就是环。最后 learned = 0，numCourses = 3，learned != numCourses，return false。

边界测试 · 切换后整段动画会重算

帧 1/12Scene 1

课程调度实验室 · 四区同步

读题

Scene 1

当前讲解文案 / 当前输入关系

读懂输入：每一组 [a,b] 都是一条必须先修的关系

每一组 [a,b] 都表示一条“必须先修”的关系。[a,b] 的意思是：要修 a，必须先修 b。主例是 numCourses=4，prerequisites=[[1,0],[2,0],[3,1],[3,2]]。

[a,b] = b 是 a 的前置课

输入关系

[1,0]：修 1 前先修 0

[2,0]：修 2 前先修 0

[3,1]：修 3 前先修 1

[3,2]：修 3 前先修 2

关键：先读人话：有些课程必须先修别的课程，我们要找有没有互相等待的死循环。

不变量：还没有进入算法术语，只确认题目在问“能不能全部修完”。

3D 课程依赖图主舞台

前置课程 → 后续课程

当前阶段：读题[1,0] → 0 → 1

graph 邻接表

graph[0][]

graph[1][]

graph[2][]

graph[3][]

graph[cur] 表示：学完 cur 后，能解锁哪些 next 课程。

indegree 入度表 / 前置锁

indegree[0]0

锁全部打开，可以学习

indegree[1]0

锁全部打开，可以学习

indegree[2]0

锁全部打开，可以学习

indegree[3]0

锁全部打开，可以学习

queue 队列 / 待修传送带

左边 pop

queue = []

右边 push

已修课程 learned

0 / 4

learned = 0 / 4

底部：Go 代码高亮

代码 · 当前高亮行随帧切换

1package main
2 
3func canFinish(numCourses int, prerequisites [][]int) bool {
4    // graph[i] 表示：学完课程 i 之后，可以继续学哪些课程
5    graph := make([][]int, numCourses)
6 
7    // indegree[i] 表示：课程 i 还有多少门前置课程没有完成
8    indegree := make([]int, numCourses)
9 
10    // 建图
11    for _, p := range prerequisites {
12        course := p[0] // 要学习的课程
13        pre := p[1]    // 前置课程
14 
15        // pre -> course
16        graph[pre] = append(graph[pre], course)
17 
18        // course 多了一个前置依赖
19        indegree[course]++
20    }
21 
22    // 找出所有入度为 0 的课程
23    // 这些课程没有前置依赖，可以直接学
24    queue := make([]int, 0)
25    for i := 0; i < numCourses; i++ {
26        if indegree[i] == 0 {
27            queue = append(queue, i)
28        }
29    }
30 
31    // 记录已经学完的课程数量
32    learned := 0
33 
34    // BFS 拓扑排序
35    for len(queue) > 0 {
36        // 取出队头课程
37        cur := queue[0]
38        queue = queue[1:]
39 
40        // 学完当前课程
41        learned++
42 
43        // 看看学完 cur 后，哪些课程的前置依赖可以减少
44        for _, next := range graph[cur] {
45            indegree[next]--
46 
47            // 如果 next 的所有前置课程都学完了
48            // 那么 next 也可以学习了
49            if indegree[next] == 0 {
50                queue = append(queue, next)
51            }
52        }
53    }
54 
55    // 如果学完的课程数量等于总课程数，说明没有环
56    return learned == numCourses
57}

代码高亮同步：读题

建立 graph

graph[pre] = append(graph[pre], course)

学完 pre 后，可以解锁 course。

计算入度

indegree[course]++

course 多了一把前置锁。

寻找起点

indegree[i] == 0

没有前置锁，进入 queue。

修课

learned++

从 queue 左侧 pop 出来的课程被修完。

解锁后续

indegree[next]--

前置锁减少一把，变 0 才 queue append。

完成判断

return learned == numCourses

全部修过就是无环，否则有环。

时间线 · 点击跳转

不变量 · 算法为什么对

graph[cur] 表示学完 cur 后能解锁哪些 next 课程。
indegree[next]-- 表示 next 的前置锁减少一把。
queue append 表示课程解锁后进入待修队列。
最后用 learned == numCourses 判断是否存在环。

复杂度 · V = numCourses，E = prerequisites.length

时间O(V + E)

建图扫一遍 prerequisites；BFS 调度时每门课最多出队一次，每条边最多让一个 indegree 减少一次。

空间O(V + E)

graph 存 E 条有向边，indegree 和 queue 最多存 V 个课程。

面试这样说

我会把课程看成有向图。[a,b] 表示 b 是 a 的前置课，所以建边 b → a。graph[i] 表示学完 i 后能解锁哪些课，indegree[i] 表示课程 i 还欠几门前置课。先把所有 indegree 为 0 的课放进 queue，每次修完一门课 learned++，再让它后续课程的 indegree--。最后 learned == numCourses 说明所有课程都修完，没有环；否则剩下课程互相等待，有环。

迁移练习

LC210 课程表 II — 不只判断能不能修，还要输出一条修课顺序
LC802 找到最终的安全状态 — 换一个角度理解图上的出入度
LC269 火星词典 — 从顺序关系建有向图

常见误区

误区 1 · [a,b] 边方向容易画反
人话是「想修 a，必须先修 b」。所以边是 b → a，表示学完 b 后才可能解锁 a；不是 a → b。
误区 2 · queue 为空不代表成功
queue 只是「当前能修的课」。它空了以后，还要看 learned == numCourses；如果 learned 更小，说明剩下课程被环卡住。
误区 3 · indegree-- 不等于立刻入队
indegree-- 只是前置锁减少一把。只有 indegree 真的变成 0，才说明所有前置课都修完，可以加入 queue。
误区 4 · 多个 indegree==0 的课程都要入队
如果课程 1 和课程 2 都已经没有前置锁，它们都可以作为下一批待修课程。不要只挑一个，否则会漏处理。
误区 5 · graph[cur] 的方向别读反
graph[cur] 不是 cur 依赖哪些课，而是学完 cur 后，能解锁哪些 next 课程。