LeetCode 207. 课程表
题目核心
给定课程数量 numCourses 和先修关系数组 prerequisites，判断是否能够修完所有课程。
每个先修关系：
[course, pre]表示学习 course 之前必须先学习 pre，对应一条有向边：
pre -> course如果课程依赖图中存在环，就会出现互相等待的课程，无法修完全部课程。因此这道题本质上是判断有向图中是否存在环。
解题思考过程
第一步：理解问题
这是一个典型的拓扑排序问题。如果图中存在环，就无法进行拓扑排序。
示例：
numCourses = 2, prerequisites = [[1,0]]
课程1依赖课程0，图：0 -> 1
可以修完：先修0，再修1 ✓
numCourses = 2, prerequisites = [[1,0],[0,1]]
课程1依赖0，课程0依赖1，图：0 <-> 1
存在环，无法修完 ✗第二步：暴力解法（DFS 判断环）
最直接的思路：对每个节点进行 DFS，记录访问路径，如果遇到已访问的节点且在当前路径中，说明有环。
visited[i] = 0: 未访问
visited[i] = 1: 正在访问（在当前路径中）
visited[i] = 2: 已访问（不在当前路径中）这就是三色标记法：
- 白色（0）：未访问
- 灰色（1）：正在访问
- 黑色（2）：已访问
第三步：DFS 三色标记的实现
dfs(node):
if visited[node] == 1: return true（有环）
if visited[node] == 2: return false（无环）
visited[node] = 1 // 标记为正在访问
for each neighbor in adj[node]:
if dfs(neighbor) == true: return true
visited[node] = 2 // 标记为已访问
return false第四步：BFS 拓扑排序
另一种思路：使用拓扑排序，每次删除入度为0的节点，如果最后还有节点未删除，说明有环。
1. 计算每个节点的入度
2. 把入度为0的节点加入队列
3. 从队列中取出节点，删除它的所有出边（邻居入度-1）
4. 如果邻居入度变为0，加入队列
5. 重复直到队列为空
6. 如果删除的节点数 < 总节点数，说明有环第五步：两种方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| DFS 三色标记 | O(V+E) | O(V) | 代码简洁 |
| BFS 拓扑排序 | O(V+E) | O(V) | 可以输出拓扑序列 |
两种方法时间复杂度相同，都是 O(V+E)。
第六步：选择最佳方案
如果只需要判断是否有环，两种方法都可以。如果需要输出拓扑序列（比如哪门课先修），BFS 更好。
当前解法：DFS 三色标记
当前代码先建立邻接表：
const graph = Array.from({ length: numCourses }, () => []);
for (const [course, pre] of prerequisites) {
graph[pre].push(course);
}然后使用 state 数组记录每门课程的搜索状态：
0：尚未访问
1：正在当前 DFS 路径中访问
2：已经完成搜索，确认从它出发没有环核心判断如下：
const hasCircle = (course) => {
if (state[course] === 1) {
return true;
}
if (state[course] === 2) {
return false;
}
state[course] = 1;
for (const nextCourse of graph[course]) {
if (hasCircle(nextCourse)) {
return true;
}
}
state[course] = 2;
return false;
};代码逐行解释
const graph = Array.from({ length: numCourses }, () => []);创建邻接表。graph[i] 是一个数组，存储所有需要先修课程 i 的课程。
for (const [course, pre] of prerequisites) {
graph[pre].push(course);
}遍历先修关系。对于每个 [course, pre]，表示学习 course 需要先学 pre，所以在 graph[pre] 中添加 course，形成一条有向边 pre -> course。
const state = new Array(numCourses).fill(0);创建状态数组，初始值为 0（尚未访问）。
const hasCircle = (course) => {定义递归函数，参数 course 表示当前正在检查的课程。函数返回 true 表示存在环，返回 false 表示没有环。
if (state[course] === 1) {
return true;
}如果当前课程状态为 1（正在当前 DFS 路径中），说明我们在递归路径中再次遇到了这个课程，形成了环。
if (state[course] === 2) {
return false;
}如果当前课程状态为 2（已经完成搜索），说明之前已经确认过从这门课程出发没有环，可以直接返回 false，避免重复搜索。
state[course] = 1;将当前课程标记为 1（正在访问），表示它已经进入当前递归路径。
for (const nextCourse of graph[course]) {
if (hasCircle(nextCourse)) {
return true;
}
}遍历当前课程的所有后继课程（需要当前课程作为先修的课程），递归检查每个后继课程是否存在环。如果任何一个后继课程返回 true，说明存在环，立即返回 true。
state[course] = 2;所有后继课程都检查完毕且没有发现环，将当前课程标记为 2（完成搜索）。
return false;
};返回 false，表示从当前课程出发没有环。
完整代码
var canFinish = function (numCourses, prerequisites) {
const graph = Array.from({ length: numCourses }, () => []);
const state = new Array(numCourses).fill(0);
for (const [course, pre] of prerequisites) {
graph[pre].push(course);
}
const hasCircle = (course) => {
if (state[course] === 1) {
return true;
}
if (state[course] === 2) {
return false;
}
state[course] = 1;
for (const nextCourse of graph[course]) {
if (hasCircle(nextCourse)) {
return true;
}
}
state[course] = 2;
return false;
};
for (let i = 0; i < numCourses; i++) {
if (hasCircle(i)) {
return false;
}
}
return true;
};为什么遇到状态 1 就说明有环
状态 1 表示课程仍在当前递归路径中。
例如依赖关系为：
0 -> 1 -> 2 -> 0从课程 0 开始 DFS 时，0、1、2 会依次标记为 1。从 2 再次访问 0 时，发现 0 仍处于当前路径中，说明路径回到了之前的节点，因此存在环。
状态 2 则表示该节点及其后续路径已经完整检查过，可以直接复用结果，不需要重复搜索。
完整流程
对所有课程分别尝试 DFS：
for (let i = 0; i < numCourses; i++) {
if (hasCircle(i)) {
return false;
}
}
return true;之所以需要遍历所有课程，是因为图中可能存在多个互不连通的部分。从一门课程开始搜索，不一定能够访问整个图。
执行过程示例
以 numCourses = 4, prerequisites = [[1,0], [2,0], [3,1], [3,2]] 为例：
graph = [[1, 2], [3], [3], []]
state = [0, 0, 0, 0]
检查课程 0：
state[0] = 1
检查课程 1：
state[1] = 1
检查课程 3：
state[3] = 1
没有后继课程，state[3] = 2，返回 false
state[1] = 2，返回 false
检查课程 2：
state[2] = 1
检查课程 3：
state[3] = 2，直接返回 false
state[2] = 2，返回 false
state[0] = 2，返回 false
检查课程 1：state[1] = 2，直接返回 false
检查课程 2：state[2] = 2，直接返回 false
检查课程 3：state[3] = 2，直接返回 false
所有课程检查完毕，返回 true（可以修完）复杂度
设课程数量为 V，先修关系数量为 E：
- 时间复杂度：
O(V + E)，每个节点和每条边最多被完整处理一次。 - 空间复杂度：
O(V + E)，邻接表、状态数组和递归调用栈都需要空间。
替代解法：BFS 拓扑排序
还可以统计每门课程的入度，把所有入度为 0 的课程加入队列。每学完一门课程，就删除它指向的边，并更新后续课程的入度。
var canFinish = function (numCourses, prerequisites) {
const graph = Array.from({ length: numCourses }, () => []);
const indegree = new Array(numCourses).fill(0);
for (const [course, pre] of prerequisites) {
graph[pre].push(course);
indegree[course]++;
}
const queue = [];
for (let i = 0; i < numCourses; i++) {
if (indegree[i] === 0) {
queue.push(i);
}
}
let learned = 0;
let front = 0;
while (front < queue.length) {
const course = queue[front++];
learned++;
for (const nextCourse of graph[course]) {
indegree[nextCourse]--;
if (indegree[nextCourse] === 0) {
queue.push(nextCourse);
}
}
}
return learned === numCourses;
};BFS 解法逐行解释
const graph = Array.from({ length: numCourses }, () => []);
const indegree = new Array(numCourses).fill(0);创建邻接表和入度数组。indegree[i] 表示课程 i 的先修课程数量。
for (const [course, pre] of prerequisites) {
graph[pre].push(course);
indegree[course]++;
}构建邻接表，并统计每门课程的入度。
const queue = [];
for (let i = 0; i < numCourses; i++) {
if (indegree[i] === 0) {
queue.push(i);
}
}把所有入度为 0 的课程加入队列，这些课程可以直接学习。
let learned = 0;
let front = 0;learned 记录已经学完的课程数量，front 是队列的头指针。
while (front < queue.length) {
const course = queue[front++];
learned++;取出队列头部的课程，标记为已学习。
for (const nextCourse of graph[course]) {
indegree[nextCourse]--;
if (indegree[nextCourse] === 0) {
queue.push(nextCourse);
}
}
}遍历当前课程的所有后继课程，将它们的入度减 1（表示一门先修课程已完成）。如果某个后继课程的入度变为 0，说明它的所有先修课程都已完成，可以加入队列等待学习。
return learned === numCourses;如果学完的课程数量等于总课程数量，说明所有课程都可以修完（无环）；否则说明存在环，某些课程无法学习。
两种解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| DFS 三色标记 | O(V + E) | O(V + E) | 更直接地判断环 |
| BFS 拓扑排序 | O(V + E) | O(V + E) | 直接模拟课程的可学习顺序 |
DFS 和 BFS 的时间、空间复杂度相同。DFS 更直接地判断环，BFS 则直接模拟课程的可学习顺序。