LeetCode 207. 课程表
题目描述
✅ 207. 课程表
题意分析
一共有
numCourses门课，编号从0到numCourses - 1。依赖关系[a, b]表示学习a之前必须先完成b。如果一门课有多个前置课程，它们必须全部完成后才能学习这门课。判断是否存在一种顺序，可以完成全部课程，只返回布尔值，不要求输出学习顺序。没有出现在依赖关系中的课程也算在总数中；如果课程互相依赖形成环，就无法找到环内第一门能够开始学习的课。
解法：入度表 + BFS 拓扑排序
核心思路
[!blue]
把课程看作节点，把先修关系
[a, b]建成有向边b -> a。graph[b]记录完成b后可能受到影响的后续课程，indegree[a]记录a尚未完成的前置课程数量。起初它等于入边数，之后会随着前置课程完成而减少。入度为
0的课当前可以学习，因此先把所有这样的课程放入队列。每次取出一门课，视为完成它，计数learned加一；再遍历它指向的每门后续课程，将剩余入度减一。只有入度恰好减到0，才能把后续课程入队，因为此时它的全部前置条件才都满足。这个过程相当于反复从图中删除一个没有入边的节点及其出边，也就是拓扑排序。每门出队课程的前置课程都已经完成，所以出队顺序始终是一段合法学习顺序。若
learned == numCourses，就确实找到了完成全部课程的方法。若队列空了但仍有课程未处理，说明剩余每门课都至少依赖另一门未处理课程。沿着这些未完成的前置关系不断追溯，因为剩余节点有限，必然会回到之前的节点，形成环。因此不可能继续完成全部课程。剩余节点既可能在环内，也可能只是依赖环，并非每个剩余节点都直接属于环。
初始化时必须扫描全部课程编号，而非只从某一门课开始，才能覆盖互不相连的依赖部分和完全没有依赖的孤立课程。答案取决于最终处理数量，而不是队列最初是否非空。
解题步骤
- 建邻接表和入度数组：对
[a,b]，加入边b -> a，并令indegree[a]++。- 扫描全部课程，把入度为
0的课程入队；孤立课程也会在这里入队。- 每次出队一门课程并增加处理数；遍历其后续课程，将对应入度减一。
- 某门后续课的入度恰好变为
0时入队，保证每门课只处理一次。- 队列为空后，判断处理数是否等于
numCourses。
代码实现
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为先修关系数。初始化和入队检查遍历全部课程；建图遍历全部边，处理课程时每条边至多再用于减少一次后续入度。- 空间复杂度：$O(V + E)$，邻接表保存
V个课程的列表和E条边，入度数组及队列各占 $O(V)$。
关键点总结
[!green]
- 先修关系
[a,b]的方向是b -> a，入度加在课程a上。- 入度为
0表示当前可执行；拓扑排序本质是不断删除这类节点。- 每门课程只在剩余入度变为零时入队一次，因此不需要另加访问集合。
- 处理数不足说明有环阻止继续学习；已完成的部分不会影响对其余依赖关系的判定。
易错点总结
[!yellow]
- 建图和入度统计必须一致：
graph[b]加入a时增加的是indegree[a]，不能一边表示后续课程、一边却统计前置课程的出度。- 初始队列非空只说明部分课程可以开始，不能证明其他依赖部分无环；必须比较最终完成数量。
- 初始化漏掉孤立课程会让计数不足，即使没有环也返回假；所有课程编号都需要检查入度。
- 完成任意一门前置课后就立即入队，会忽略尚未完成的其他前置要求；只有剩余入度为零才可入队。
- Java 的邻接表数组创建后，每个元素仍为
null，添加边之前必须逐个创建列表。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 210. 课程表 II | 中等 | 依赖图相同，原题不仅判定无环，还需要输出实际课程顺序。 |
| 802. 找到最终的安全状态 | 中等 | 同样分析有向图中的环；802逐节点判断从它出发的所有路径是否最终终止，只要能进入环就不安全，本题则判断整张课程依赖图是否无环。 |
| 269. 火星词典 | 困难 | 用拓扑排序处理有向依赖关系；本题判断是否能移除全部节点以检测环，该题从单词相邻关系提取字符先后约束。 |
| 1462. 课程表 IV | 中等 | 课程表系列。I 判断先修图是否有环；IV 回答任意两门课之间的先修关系，需要预处理可达性。 |