题目描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。
在选修某些课程之前需要先修另外一些课程。 先修关系由数组 prerequisites 给出，其中：
prerequisites[i] = [a, b]
表示如果想学课程 a，必须先学课程 b。
现在请你判断：是否可能完成所有课程的学习？
题目本质
这道题表面上看是在讲课程安排，实际上本质是一个有向图判环问题。
我们可以把每门课程看成图中的一个节点。
如果想学课程 a 之前必须先学课程 b，那么就连一条有向边：
b -> a
意思是：学完 b 之后，才可以学 a。
那么问题就变成了：
这张有向图中是否存在环？
因为：
-
如果有环，比如
0 -> 1 -> 2 -> 0 -
那么你想学 0 之前要先学 2
-
想学 2 之前要先学 1
-
想学 1 之前又要先学 0
这样就形成了死循环，课程永远学不完。
所以这道题其实就是：
-
无环：可以完成所有课程
-
有环：不能完成所有课程
这道题的两种经典解法
你给出的代码正好是这道题最经典的两种做法：
-
BFS + 拓扑排序
-
DFS + 判环
虽然写法不同，但核心目标都是一样的：
判断图中是否有环。
下面分别来讲。
方法一：BFS + 拓扑排序
核心思路
拓扑排序适用于有向无环图（DAG）。
如果一张图能够完成拓扑排序，说明这张图没有环。 如果无法完成拓扑排序，说明图中存在环。
在这道题里，我们维护每门课程的入度：
-
入度表示：有多少门前置课程还没有学完
然后：
-
先把所有入度为 0 的课程加入队列 这些课程表示没有任何前置要求，可以直接学
-
每次从队列中取出一门课程，表示学完了它
-
然后把它指向的后续课程入度减 1
-
如果某门课的入度减到 0，说明它的前置课程都已经完成，就可以入队
-
最后如果所有课程都能被处理完，说明没有环；否则说明有环
BFS 代码
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indegrees = new int[numCourses];
List<List<Integer>> adjacency = new ArrayList<>();
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < numCourses; i++)
adjacency.add(new ArrayList<>());
for(int[] cp : prerequisites) {
indegrees[cp[0]]++;
adjacency.get(cp[1]).add(cp[0]);
}
for(int i = 0; i < numCourses; i++)
if(indegrees[i] == 0) queue.add(i);
while(!queue.isEmpty()) {
int pre = queue.poll();
numCourses--;
for(int cur : adjacency.get(pre))
if(--indegrees[cur] == 0) queue.add(cur);
}
return numCourses == 0;
}
}
代码解析
1. 定义入度数组、邻接表和队列
int[] indegrees = new int[numCourses];
List<List<Integer>> adjacency = new ArrayList<>();
Queue<Integer> queue = new LinkedList<>();
-
indegrees[i]：课程i的入度 -
adjacency：邻接表，用来存图 -
queue：保存当前所有入度为 0 的课程
2. 初始化邻接表
for(int i = 0; i < numCourses; i++)
adjacency.add(new ArrayList<>());
为每一门课程准备一个列表，用来存它能通向哪些后续课程。
3. 建图并统计入度
for(int[] cp : prerequisites) {
indegrees[cp[0]]++;
adjacency.get(cp[1]).add(cp[0]);
}
这里 cp = [a, b]，表示：
b -> a
所以：
-
a的入度加 1 -
在
b的邻接表中加入a
4. 把所有入度为 0 的节点加入队列
for(int i = 0; i < numCourses; i++)
if(indegrees[i] == 0) queue.add(i);
这些课程没有前置要求，可以直接学习。
5. 不断从队列中取课程
while(!queue.isEmpty()) {
int pre = queue.poll();
numCourses--;
每取出一门课程，就表示已经成功学完一门课，所以 numCourses--。
这里把 numCourses 当成“还剩多少门课没处理”。
6. 更新后续课程的入度
for(int cur : adjacency.get(pre))
if(--indegrees[cur] == 0) queue.add(cur);
如果某门后续课程的入度减为 0，说明它的所有前置课程都已经学完了，就可以加入队列。
7. 判断是否全部处理完成
return numCourses == 0;
如果最终所有课程都处理完了，说明图中没有环。 否则说明还有课程无法进入队列，也就是图中存在环。
BFS 示例推演
示例 1
numCourses = 2
prerequisites = [[1,0]]
表示：
0 -> 1
初始状态：
-
入度数组：
[0,1] -
队列中先加入
0
处理过程：
-
取出
0，剩余课程数减 1 -
让
1的入度减 1，变成 0 -
把
1加入队列 -
再取出
1
最终所有课程都处理完成，返回 true。
示例 2
numCourses = 2
prerequisites = [[1,0],[0,1]]
表示：
0 -> 1
1 -> 0
初始状态：
-
入度数组：
[1,1] -
没有任何课程入度为 0
所以队列一开始就是空的，无法开始学习。 最终 numCourses 不为 0，返回 false。
这就说明图中有环。
方法二：DFS + 判环
核心思路
第二种做法是深度优先搜索。
既然题目本质是在判断图中有没有环，那么 DFS 很自然也能解决。
这里最关键的是： 我们需要知道一个节点在 DFS 过程中处于什么状态。
所以用一个 flags 数组来记录每个节点的访问状态：
-
0：还没有访问过 -
1：当前正在访问中 -
-1：已经访问完成，且这条路径没有问题
为什么这样可以判断环
在 DFS 的过程中：
-
如果我们访问到一个节点，它的状态是
1 -
说明这个节点正在当前这条递归路径上
-
这意味着我们从当前节点又绕回来了
于是就发现了一个环。
所以：
在 DFS 中，如果遇到状态为
1的节点，说明图中有环。
DFS 代码
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adjacency = new ArrayList<>();
for(int i = 0; i < numCourses; i++)
adjacency.add(new ArrayList<>());
int[] flags = new int[numCourses];
for(int[] cp : prerequisites)
adjacency.get(cp[1]).add(cp[0]);
for(int i = 0; i < numCourses; i++)
if(!dfs(adjacency, flags, i)) return false;
return true;
}
private boolean dfs(List<List<Integer>> adjacency, int[] flags, int i) {
if(flags[i] == 1) return false;
if(flags[i] == -1) return true;
flags[i] = 1;
for(Integer j : adjacency.get(i))
if(!dfs(adjacency, flags, j)) return false;
flags[i] = -1;
return true;
}
}
代码解析
1. 初始化邻接表
List<List<Integer>> adjacency = new ArrayList<>();
for(int i = 0; i < numCourses; i++)
adjacency.add(new ArrayList<>());
和 BFS 方法一样，这里也是先建图。
2. 定义访问状态数组
int[] flags = new int[numCourses];
-
0：未访问 -
1：当前递归路径中 -
-1：已经访问过，并确认无环
3. 建图
for(int[] cp : prerequisites)
adjacency.get(cp[1]).add(cp[0]);
同样是：
b -> a
表示学完 b 才能学 a。
4. 对每个节点做 DFS
for(int i = 0; i < numCourses; i++)
if(!dfs(adjacency, flags, i)) return false;
因为图可能不是连通的，所以每个节点都要尝试 DFS。
只要某一次 DFS 发现环，就直接返回 false。
5. DFS 的判环逻辑
if(flags[i] == 1) return false;
if(flags[i] == -1) return true;
这是最核心的地方。
-
如果
flags[i] == 1，说明当前节点正在递归路径中，又被访问到了，说明有环 -
如果
flags[i] == -1，说明这个节点之前已经搜过了，而且确定没问题，直接返回true
6. 标记当前节点为“正在访问”
flags[i] = 1;
表示当前节点已经进入递归栈。
7. 继续 DFS 相邻节点
for(Integer j : adjacency.get(i))
if(!dfs(adjacency, flags, j)) return false;
只要后续有任何一个节点发现环，就立刻返回 false。
8. 搜索完成后标记为“已确认无环”
flags[i] = -1;
return true;
说明从当前节点出发的整条路径都没有问题。
DFS 示例推演
假设有依赖关系：
0 -> 1
1 -> 2
2 -> 0
进行 DFS：
-
访问
0，标记为1 -
访问
1，标记为1 -
访问
2，标记为1 -
再访问
0时，发现flags[0] == 1
说明 0 还在当前递归路径上，又被访问到了，所以图中存在环。
直接返回 false。
两种方法的本质
其实这两种方法虽然形式不同，但本质都是在判断有向图中是否存在环。
BFS 拓扑排序
-
通过不断删除入度为 0 的节点
-
如果最后删不完，说明存在环
DFS 判环
-
通过递归搜索路径
-
如果在当前路径中再次访问到某个节点，说明存在环
所以你可以把它们理解成两种不同角度的“判环”。
两种方法对比
BFS 拓扑排序
优点：
-
思路直观
-
容易结合“先修课程”的业务含义理解
-
同时还能得到一条合法的学习顺序（如果题目要求的话）
缺点：
-
需要额外维护入度数组和队列
DFS 判环
优点：
-
判环逻辑很直接
-
写法紧凑
缺点：
-
第一次接触时，对
flags三种状态不太容易理解
复杂度分析
设课程数为 V，先修关系数为 E。
BFS 方法
-
时间复杂度：
O(V + E) -
空间复杂度：
O(V + E)
DFS 方法
-
时间复杂度：
O(V + E) -
空间复杂度：
O(V + E)
两种方法本质上都要遍历整张图，所以复杂度相同。
总结
这道题最关键的一点就是：
课程表问题，本质就是有向图判环问题。
只要图中没有环，就说明课程依赖关系合法，可以学完所有课。 只要图中有环，就一定会出现互相依赖，导致无法完成课程。
你给出的两种解法都非常经典：
-
BFS + 拓扑排序：看能不能把所有课程都“删掉”
-
DFS + 判环：看递归过程中会不会回到当前路径上的节点
如果是面试或者刷题，建议这两种方法都掌握，因为这是图论里最基础也最常考的题型之一。
