LeetCode 210. 课程表 II
题目描述
题意分析
课程编号为
0到numCourses - 1，依赖对[course, pre]表示必须先完成pre，才能学习course。需要返回包含每门课程恰好一次的学习顺序，并让所有先修关系都得到满足。同一组依赖可能允许多种顺序，返回任意一种即可，不要求字典序最小。没有依赖的课程也必须出现在结果中；如果循环依赖导致无法完成全部课程，应返回空数组，不能只返回其中已经能学的部分。
解法：BFS 拓扑排序
核心思路
[!blue]
将课程视为有向图的节点，先修关系建立为
pre → course。这样一门课完成之后，沿它的出边就能找到受到影响的后续课程。indegree[course]表示当前还没有完成的直接先修课程数，初始由全部依赖统计得到。入度为零的课程没有剩余先修条件，可以安全地作为下一门课。先把所有这样的课程加入队列；每次出队就把这门课写入答案，再遍历它的后续课程，将对应入度减一。当某门后续课的入度恰好降到零时，表示所有先修课都已写入答案，此时才把它加入队列。
因此每次输出都发生在该课程的全部先修课程之后，构造出的前缀始终满足依赖关系。多个零入度课程同时可选，它们的先后顺序可以不同；初始化时扫描全部课程，才能同时覆盖孤立课程和彼此独立的图分量。
队列为空后，如果还剩未输出课程，则这些课程在剩余图中都有至少一条未解除的入边。沿未完成的先修关系不断向前追溯，在有限节点中必然重复到达某个节点，也就存在有向环。环上的课程相互等待，可能连带阻塞环后面的课程，因此只有输出数量等于总课程数时，才能返回完整学习顺序。
解题步骤
- 为每门课程建立后续课程列表，按
pre → course添加边，同时增加course的入度。- 遍历所有课程，将初始入度为零的课程加入队列。
- 依次取出队首课程并加入答案，遍历它的每条出边，使后续课程入度减一。
- 仅当后续课程入度降到零时入队，继续上述过程。
- 比较实际输出数量与
numCourses：全部输出则返回顺序，否则返回空数组。
代码实现
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
int[] indegree = new int[numCourses];
for (int[] edge : prerequisites) {
graph.get(edge[1]).add(edge[0]);
indegree[edge[0]]++;
}
Queue<Integer> queue = new ArrayDeque<>();
for (int course = 0; course < numCourses; course++) {
if (indegree[course] == 0) {
queue.offer(course);
}
}
int[] order = new int[numCourses];
int idx = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
order[idx++] = course;
for (int next : graph.get(course)) {
// 所有前置完成时才释放下一课程，不能第一次见到就入队。
if (--indegree[next] == 0) {
queue.offer(next);
}
}
}
// 必须输出全部课程，剩余未处理节点表示存在循环依赖。
return idx == numCourses ? order : new int[0];
}
}
func findOrder(numCourses int, prerequisites [][]int) []int {
graph := make([][]int, numCourses)
indegree := make([]int, numCourses)
for _, edge := range prerequisites {
course := edge[0]
pre := edge[1]
graph[pre] = append(graph[pre], course)
indegree[course]++
}
queue := make([]int, 0)
for course := 0; course < numCourses; course++ {
if indegree[course] == 0 {
queue = append(queue, course)
}
}
order := make([]int, 0, numCourses)
for head := 0; head < len(queue); head++ {
course := queue[head]
order = append(order, course)
for _, next := range graph[course] {
indegree[next]--
// 所有前置完成时才释放下一课程，不能第一次见到就入队。
if indegree[next] == 0 {
queue = append(queue, next)
}
}
}
// 必须输出全部课程，剩余未处理节点表示存在循环依赖。
if len(order) != numCourses {
return []int{}
}
return order
}
复杂度分析
- 时间复杂度：$O(n + m)$，
n为课程数，m为依赖数；建图扫描全部边，每个节点至多入队一次，每条边再处理一次。- 空间复杂度：$O(n + m)$，邻接表保存节点列表与全部边，入度、队列和结果各需要 $O(n)$ 空间。
关键点总结
[!green]
- 建边方向是先修课指向后续课程，与最终学习顺序一致。
- 入度是动态的“尚未完成先修课数量”，不是固定不变的原始度数。
- 每次只输出零入度节点，保证已经生成的顺序始终满足全部先修关系。
- 无法输出所有节点，说明剩余依赖中存在环；顺序可以不唯一，完整性不能省略。
易错点总结
[!yellow]
- 把边建成后续课指向先修课，却仍直接输出当前拓扑序，会把学习先后关系反过来。
- 只选一个初始零入度节点，会遗漏没有连到它的其他分量或孤立课程。
- 后续课程第一次被遇到就入队，没有等其他先修课全部完成，会提前输出它。
- 入度没有刚好降到零也重复入队，可能重复输出同一课程。
- 不比较最终输出数量，会把有环时的部分结果误当成完整答案。
- 要求输出与某一个固定序列完全一致，会误判其他同样满足全部依赖的合法顺序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 207. 课程表 | 中等 | 依赖图相同，原题只判断能否完成，本题还需输出一个合法拓扑顺序。 |
| 802. 找到最终的安全状态 | 中等 | 同样可用度数逐步剥离节点，原题在反图中从终点消除安全节点。 |
| 269. 火星词典 | 困难 | 用拓扑排序处理有向依赖关系；本题输出合法的课程顺序，该题从单词相邻关系提取字符先后约束。 |
| 1462. 课程表 IV | 中等 | 课程表系列。II 输出一个合法拓扑序；IV 预处理先修路径，回答多次两点可达性查询。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！