LeetCode 207. 课程表
目录
题目描述
✅ 207. 课程表
题意分析
给定
numCourses门课（编号0到numCourses - 1）和一组先修关系prerequisites，问能否修完全部课程，返回布尔值。注意题目只问「能不能」，不要求给出具体的修课顺序。先看清方向约定：
prerequisites[i] = [a, b]表示想学a必须先学b，也就是依赖关系是b -> a（先修课指向后续课）。这个方向极易搞反，动手前必须先固定下来。关键转化：每门课是一个点，每条先修关系是一条有向边，「能否修完所有课」就等价于「这张依赖图里是否不存在环」——一旦出现
a依赖b、b又（直接或间接）依赖a，这两门课谁也无法开始。约束信号：课程数最多 $2000$、先修关系最多 $5000$，说明只要对点和边做线性级别的处理就够了。边界上要注意
prerequisites可能为空（必然能修完），以及可能存在不出现在任何先修关系里的孤立课程。
解法：入度表 + BFS 拓扑排序
核心思路
问题关键：
[a,b]表示边b -> a，题目等价于判断这张有向图是否有环。这里选择 BFS 拓扑排序，因为状态只有邻接表、入度和队列，面试中容易写对。入度表示一门课还剩多少前置课程。先把所有入度为
0的课程入队；每学完一门课，就把它指向的后续课程入度减一，新降为0的课程继续入队。不变量是：队列中始终只包含前置条件已经全部满足的课程。环上的节点互相依赖，入度无法被削减到
0，因此不会被处理。最终处理数等于课程总数说明无环；否则剩余节点必在环中或依赖某个环。DFS 三色标记也能判环，但不是本题主解法。
解题步骤
- 建邻接表和入度数组：对
[a,b]，加入边b -> a，并令indegree[a]++。- 扫描全部课程，把入度为
0的课程入队；孤立课程也会在这里入队。- 每次出队一门课程并增加处理数；遍历其后续课程，将对应入度减一。
- 某门后续课的入度恰好变为
0时入队，保证每门课只处理一次。- 队列为空后，判断处理数是否等于
numCourses。例如
[[1,0],[2,0],[3,1],[3,2]]的初始入度为[0,1,1,2]：先处理0，解锁1、2；二者都处理后才解锁3，最终处理 4 门课，返回true。
代码实现
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = new ArrayList[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList<>();
}
int[] indegree = new int[numCourses];
for (int[] edge : prerequisites) {
graph[edge[1]].add(edge[0]);
indegree[edge[0]]++;
}
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
int learned = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
learned++;
// 学完当前课程后，释放依赖它的后续课程。
for (int next : graph[course]) {
indegree[next]--;
if (indegree[next] == 0) {
queue.offer(next);
}
}
}
return learned == numCourses;
}
}
func canFinish(numCourses int, prerequisites [][]int) bool {
graph := make([][]int, numCourses)
indegree := make([]int, numCourses)
for _, edge := range prerequisites {
graph[edge[1]] = append(graph[edge[1]], edge[0])
indegree[edge[0]]++
}
queue := make([]int, 0)
for i := 0; i < numCourses; i++ {
if indegree[i] == 0 {
queue = append(queue, i)
}
}
learned := 0
for len(queue) > 0 {
course := queue[0]
queue = queue[1:]
learned++
// 当前课程完成后，后续课程的剩余依赖减少。
for _, next := range graph[course] {
indegree[next]--
if indegree[next] == 0 {
queue = append(queue, next)
}
}
}
return learned == numCourses
}
复杂度分析
- 时间复杂度：$O(V + E)$，其中 $V$ 为课程数、$E$ 为先修关系数。建图扫一遍所有边；BFS 中每门课至多入队出队一次，每条边只在其起点出队时被松弛一次。
- 空间复杂度：$O(V + E)$，邻接表存所有边占 $O(E)$，入度数组和队列各占 $O(V)$。
关键点总结
- 先修关系
[a,b]的方向是b -> a，入度加在课程a上。- 入度为
0表示当前可执行；拓扑排序本质是不断删除这类节点。- 处理数不足即可判环；若要输出课程顺序，只需记录出队序列。
- DFS 三色法是等价替代：递归中遇到灰色节点说明回到当前路径，存在环。
易错点总结
- 边方向写反：
[1,0]应建0 -> 1，并增加1的入度。方向与入度必须配套。- 只判断初始队列非空：
0可学不代表其余课程无环，如[[1,0],[2,1],[1,2]]仍然不能全部完成。- 漏掉孤立课程：初始化必须遍历
0..numCourses-1；prerequisites = []时所有课程都应入队。- 入度未降到 0 就入队：
[[2,0],[2,1]]中课程2必须等两个前置都完成，只能在入度恰好为0时入队。- 邻接表元素未初始化：Java 的
graph[i]默认是null，建边前要逐个创建列表。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 210. 课程表 II | 中等 | 在判环基础上按出队顺序输出一个可行拓扑序 |
| 269. 火星词典 | 困难 | 先从相邻单词对比较中建边，再做拓扑排序 |
| 310. 最小高度树 | 中等 | 无向图版「剥洋葱」，按度为 1 逐层删叶节点 |
| 444. 序列重建 | 中等 | 判断拓扑序是否唯一：队列中任意时刻至多一个元素 |
| LCR 113. 课程表 II | 中等 | 210 的镜像题，练习输出拓扑序的模板 |
| LCR 114. 火星词典 | 困难 | 269 的镜像题，建图正确性是主要难点 |
| LCR 115. 序列重建 | 中等 | 444 的镜像题，唯一性判定条件的推导 |
| 面试题 04.01. 节点间通路 | 中等 | 有向图两点连通性，BFS/DFS 可达性而非判环 |
| 补充题 23. 检测循环依赖 | 中等 | 工程场景包装的判环，需自己抽象出点和边 |