📝 题目描述
题目链接：课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a_i, b_i] ，表示如果要学习课程 a_i 则 必须 先学习课程 b_i 。
- 例如，先修课程对
[0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例：
1
2
3
4
5
6
7
8
9
10
11
| 示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
|
提示：
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= a_i, b_i < numCoursesprerequisites[i] 中的所有课程对 互不相同
💡 解题思路
方法一：深度优先搜索
这个题目其实本质上就是在 判断图中是否有环，如果有环，那么课程之间就会形成死锁，导致无法修完全部课程。
因此我们可以先通过题目所给的先修条件，通过邻接表构建一个有向图。
接下来，我们开始通过深度优先搜索遍历这个图，这里我们构建一个标记数组 visited，其中 0 表示未访问、1 表示访问中、2 表示已访问。
在一次深度优先搜索中，如果我们从节点 A 出发开始进行搜索，那么我们先将其标记为 1 表示我们从 A 出发且还未返回，如果在搜索的过程中回到了 A，则显然图中存在环，无法完成全部课程。
方法二：Kahn 算法（基于 BFS 的拓扑排序）
我们考虑拓扑排序中最前面的节点，该节点一定不会有任何入边，也就是它没有任何的先修课程要求。当我们将一个节点加入答案中后，我们就可以移除它的所有出边，代表着它的相邻节点少了一门先修课程的要求。如果某个相邻节点变成了“没有任何入边的节点”，那么就代表着这门课可以开始学习了。按照这样的流程，我们不断地将没有入边的节点加入答案，直到答案中包含所有的节点（得到了一种拓扑排序）或者不存在没有入边的节点（图中包含环）。
具体流程如下：
- 统计每门课的入度（即这门课有几门先修课）。
- 将所有入度为 0 的课（没有任何前提条件，可以直接学的课）放入队列。
- 从队列中取出一门课，将它指向的所有后续课程的入度减 1（代表它们的一个前置条件已经满足了）。
- 如果有后续课程的入度减到了 0，就把它们也加入队列。
- 遍历结束后，如果学完的课程数等于 numCourses，说明可以学完（无环）；否则说明图中有环。
🔧 代码实现
1、深度优先搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
public:
vector<vector<int>> graph;
vector<int> visited;
bool haveCircle = false;
void buildGraph(int numCourses, vector<vector<int>>& prerequisites) {
graph.resize(numCourses);
for (auto course : prerequisites) {
graph[course[1]].push_back(course[0]);
}
}
void dfs(int u) {
visited[u] = 1;
for (auto& v : graph[u]) {
if (visited[v] == 0) {
dfs(v);
} else if (visited[v] == 1) {
haveCircle = true;
return;
} else {
continue;
}
}
visited[u] = 2;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
buildGraph(numCourses, prerequisites);
visited.assign(numCourses, 0);
for (int i = 0; i < numCourses; i++) {
if ((visited[i] == 0) && (!haveCircle)) {
dfs(i);
}
}
return !haveCircle;
}
};
|
2、Kahn 算法（基于 BFS 的拓扑排序）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> inDegree(numCourses, 0);
vector<vector<int>> graph(numCourses);
for (const auto& pre : prerequisites) {
graph[pre[1]].push_back(pre[0]);
inDegree[pre[0]]++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
int learnedCourses = 0;
while (!q.empty()) {
int current = q.front();
q.pop();
learnedCourses++;
for (int nextCourse : graph[current]) {
inDegree[nextCourse]--;
if (inDegree[nextCourse] == 0) {
q.push(nextCourse);
}
}
}
return learnedCourses == numCourses;
}
};
|
📊 复杂度分析
1、深度优先搜索
- 时间复杂度：O(V+E)，其中 V 为课程数，E 为先修课程对的数量。构建邻接表需要 O(E)，DFS 遍历每个节点和每条边最多一次，需要 O(V+E)。
- 空间复杂度：O(V+E)。邻接表 graph 占用 O(V+E) 的空间，visited 数组占用 O(V) 的空间，最坏情况下（图退化为链表）递归调用栈的深度会达到 O(V)。
2、Kahn 算法（基于 BFS 的拓扑排序）
- 时间复杂度：O(V+E)，其中 V 为课程数，E 为先修课程的要求数，这其实就是对图进行广度优先搜索的时间复杂度。
- 空间复杂度：O(V+E)。题目中是以列表形式给出的先修课程关系，为了对图进行广度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 O(V+E)。在广度优先搜索的过程中，我们需要最多 O(V) 的队列空间（迭代）进行广度优先搜索，因此总空间复杂度为 O(V+E)。
🎯 总结
- 核心思想：理解图的搜索方法，以及学会判断图中是否有环。
