01、课程表
大约 8 分钟数据结构算法算法基地面试图论拓扑排序BFSDFS有向图环检测刷题程序厨校招社招
今天给大家说一下课程表这个题目
https://leetcode.cn/problems/course-schedule/description/
题目描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。
在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi]，表示如果要学习课程 ai 则必须先学习课程 bi。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true；否则，返回 false。
示例 1:
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。这是可能的。
示例 2:
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；
并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
示例 3:
输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：true
解释：
课程 1 需要先完成课程 0
课程 2 需要先完成课程 0
课程 3 需要先完成课程 1 和课程 2
可能的学习顺序：0 -> 1 -> 2 -> 3 或 0 -> 2 -> 1 -> 3
约束条件:
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites[i]中的所有课程对互不相同
读到这里，大家是不是已经读懂题目啦，做这个题目之前，要了解图的基本概念
我们先来分析下，课程依赖关系
课程依赖关系 = 有向图
示例：prerequisites = [[1,0],[2,0],[3,1],[3,2]]
含义：[1,0] 表示课程1依赖课程0（要学1必须先学0）
暂时无法在飞书文档外展示此内容
箭头含义：
0 → 1: 课程0是课程1的先修课（学1前要先学0）
0 → 2: 课程0是课程2的先修课
1 → 3: 课程1是课程3的先修课
2 → 3: 课程2是课程3的先修课
可能的学习顺序（拓扑排序）：
0 → 1 → 2 → 3 ✓
0 → 2 → 1 → 3 ✓
入度的概念
入度（In-degree）： 指向该节点的边的数量 各节点的入度：
- 节点0: 入度 = 0（没有箭头指向它）
- 节点1: 入度 = 1（只有0指向它）
- 节点2: 入度 = 1（只有0指向它）
- 节点3: 入度 = 2（1和2都指向它）
关键规律： 入度为0的节点 = 没有先修课程 = 可以直接学习！
为什么有环就不能完成所有课程？
示例：prerequisites = [[1,0],[0,1]]
形成的图：
0 ←───→ 1
这是一个环（循环依赖）：
- 要学课程0，必须先学课程1
- 要学课程1，必须先学课程0
- 陷入死循环！无法完成任何课程
入度分析：
节点0: 入度 = 1（1指向0）
节点1: 入度 = 1（0指向1）
没有入度为0的节点 → 无法开始学习 → 返回 false
解题思路
方法一：拓扑排序（BFS + 入度）⭐
核心思想
使用 BFS + 入度的方法进行拓扑排序：
- 计算所有节点的入度
- 将所有入度为 0 的节点加入队列（这些课程可以直接学）
- 每次从队列取出一个节点，表示学完这门课
- 将该节点的所有邻接节点的入度减 1（移除依赖）
- 如果某个邻接节点的入度变为 0，加入队列
- 重复步骤 3-5，直到队列为空
- 如果学完的课程数等于总课程数，返回 true；否则返回 false
详细图解示例
以示例3为例：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
暂时无法在飞书文档外展示此内容
步骤0: 构建图和入度数组
图的邻接表：
0 -> [1, 2]
1 -> [3]
2 -> [3]
3 -> []
入度数组：
indegree[0] = 0 （没有箭头指向0）
indegree[1] = 1 （0 -> 1）
indegree[2] = 1 （0 -> 2）
indegree[3] = 2 （1 -> 3, 2 -> 3）
步骤1: 初始化队列
找到所有入度为0的节点：节点0
队列: [0]
已学课程数: 0
步骤2: 处理节点0
取出节点0，已学课程数 = 1
处理0的邻接节点：
- 节点1: 入度 1-1=0，加入队列
- 节点2: 入度 1-1=0，加入队列
队列: [1, 2]
已学课程数: 1
更新后的入度：
indegree[1] = 0
indegree[2] = 0
indegree[3] = 2
步骤3: 处理节点1
取出节点1，已学课程数 = 2
处理1的邻接节点：
- 节点3: 入度 2-1=1，不加入队列（这里注意哈，初始入度为2）
队列: [2]
已学课程数: 2
更新后的入度：
indegree[3] = 1
步骤4: 处理节点2
取出节点2，已学课程数 = 3
处理2的邻接节点：
- 节点3: 入度 1-1=0，加入队列
队列: [3]
已学课程数: 3
更新后的入度：
indegree[3] = 0
步骤5: 处理节点3
取出节点3，已学课程数 = 4
节点3没有邻接节点
队列: []
已学课程数: 4
步骤6: 检查结果
已学课程数 4 == 总课程数 4
返回 true ✓
学习顺序: 0 -> 1 -> 2 -> 3
代码实现
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
// 构建图的邻接表
vector<vector<int>> graph(numCourses);
// 计算每个节点的入度
vector<int> indegree(numCourses, 0);
for (const auto& pre : prerequisites) {
int course = pre[0];
int prerequisite = pre[1];
// prerequisite -> course
graph[prerequisite].push_back(course);
indegree[course]++;
}
// 将所有入度为0的节点加入队列
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
// BFS 拓扑排序
int completed = 0; // 已完成的课程数
while (!q.empty()) {
int course = q.front();
q.pop();
completed++;
// 遍历该课程的所有后续课程
for (int nextCourse : graph[course]) {
indegree[nextCourse]--;
// 如果后续课程的入度变为0，加入队列
if (indegree[nextCourse] == 0) {
q.push(nextCourse);
}
}
}
// 判断是否完成所有课程
return completed == numCourses;
}
};
时间复杂度: O(V + E)
- V 是课程数（节点数）
- E 是先修关系数（边数）
- 构建图：O(E)
- BFS 遍历：每个节点和每条边都只访问一次，O(V + E)
空间复杂度: O(V + E)
- 邻接表：O(E)
- 入度数组：O(V)
- 队列：O(V)
方法二：DFS + 环检测
核心思想
使用 DFS 检测有向图中是否存在环：
- 使用三种状态标记节点：未访问、访问中、已访问
- 如果在 DFS 过程中遇到"访问中"的节点，说明有环（有环则代表无法完全访问一遍）
代码实现
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
// 构建图的邻接表
vector<vector<int>> graph(numCourses);
for (const auto& pre : prerequisites) {
graph[pre[1]].push_back(pre[0]);
}
// 节点状态：0=未访问，1=访问中，2=已访问
vector<int> state(numCourses, 0);
// 对每个节点进行 DFS
for (int i = 0; i < numCourses; i++) {
if (hasCycle(graph, state, i)) {
return false; // 发现环
}
}
return true; // 没有环
}
private:
/**
* DFS 检测是否有环
*
* @param graph 图的邻接表
* @param state 节点状态数组
* @param course 当前课程
* @return 如果有环返回 true，否则返回 false
*/
bool hasCycle(vector<vector<int>>& graph, vector<int>& state, int course) {
// 如果节点已经访问过，直接返回
if (state[course] == 2) {
return false; // 已访问，无环
}
// 如果节点正在访问中，说明遇到了环
if (state[course] == 1) {
return true; // 访问中，有环！
}
// 标记为访问中
state[course] = 1;
// 递归访问所有邻接节点
for (int nextCourse : graph[course]) {
if (hasCycle(graph, state, nextCourse)) {
return true; // 发现环
}
}
// 标记为已访问
state[course] = 2;
return false; // 没有环
}
};
时间复杂度: O(V + E)
空间复杂度: O(V + E)
