LeetCode 207. 课程表（Course Schedule）Java 实现
题目简述
一共有
“numCourses” 门课程，编号
“0 ~ numCourses-1”。给定
“prerequisites” 数组，其中
“prerequisites[i] = [a, b]” 表示 想学课程 a 必须先学课程 b。判断是否能完成所有课程。
本质：判断有向图中是否存在环（有环则无法完成）。
思路：拓扑排序（BFS / Kahn 算法）
核心思想
- 统计每门课的入度（有多少先修依赖）
- 把所有入度为 0 的课入队（不依赖任何课的课）
- 逐个出队，"学完"该课后把它指向的课的入度减 1
- 如果某门课入度变为 0，加入队列
- 最终学完的课数 == 总课数，则无环，可以学完
Java 实现
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 入度数组：indegree[i] 表示学课程 i 前需要先学的课程数
int[] indegree = new int[numCourses];
// 邻接表：graph[i] 存的是学了课程 i 之后可以学的课程列表
List<List> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
// 构建图和入度 for (int[] pre : prerequisites) { int course = pre[0]; // 想学的课 int need = pre[1]; // 先修的课 graph.get(need).add(course); indegree[course]++; } // 把所有入度为 0 的课加入队列 Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < numCourses; i++) { if (indegree[i] == 0) { queue.offer(i); } } int finished = 0; // 已学完的课数 while (!queue.isEmpty()) { int curr = queue.poll(); finished++; // 学完 curr，它指向的所有课的入度减 1 for (int next : graph.get(curr)) { indegree[next]--; if (indegree[next] == 0) { queue.offer(next); } } } // 全部学完说明无环 return finished == numCourses; }}
复杂度分析
维度 复杂度
时间 O(V + E)，V 为课程数，E 为先修关系数
空间 O(V + E)，邻接表 + 入度数组
示例说明
输入: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出: true
解释: 合理顺序如 0 → 1 → 2 → 3（或 0 → 2 → 1 → 3）
输入: numCourses = 2, prerequisites = [[1,0],[0,1]]
输出: false
解释: 0 依赖 1，1 依赖 0，形成环，无法完成
常见坑点
- 入度含义别搞反：
“[a, b]” 是 a 依赖 b，所以 b 指向 a，a 的入度 +1 - 邻接表存的是"学完某课后能学的课"，方向别存反
“finished == numCourses” 是判断无环的关键，不用人为计数边数
延伸
- DFS 三色标记法 也能判环（白/灰/黑），思路和 BFS 等价
- 如果题目问 输出一个合法的修课顺序，那就是 LeetCode 210. 课程表 II，只需把
“finished” 换成记录顺序的数组即可
需要我补充 DFS 判环版 或 LeetCode 210 输出拓扑排序 的 Java 实现吗？
