207. 课程表
207. 课程表
🟠 🔖 深度优先搜索
广度优先搜索
图
拓扑排序
🔗 力扣
LeetCode
题目
There are a total of numCourses
courses you have to take, labeled from 0
to numCourses - 1
. You are given an array prerequisites
where prerequisites[i] = [ai, bi]
indicates that you must take course bi
first if you want to take course ai
.
- For example, the pair
[0, 1]
, indicates that to take course0
you have to first take course1
.
Return true
if you can finish all courses. Otherwise, return false
.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Constraints:
1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
- All the pairs prerequisites[i] are unique.
题目大意
你这个学期必须选修 numCourses
门课程,记为 0
到 numCourses - 1
。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites
给出,其中 prerequisites[i] = [ai, bi]
,表示如果要学习课程 ai
则 必须 先学习课程 bi
。
例如,先修课程对 [0, 1]
表示:想要学习课程 0
,你需要先完成课程 1
。
请你判断是否可能完成所有课程的学习?如果可以,返回 true
;否则,返回 false
。
解题思路
什么时候无法修完所有课程?当存在循环依赖的时候。
其实这种场景在现实生活中也十分常见,比如我们写代码 import 包也是一个例子,必须合理设计代码目录结构,否则会出现循环依赖,编译器会报错,所以编译器实际上也使用了类似算法来判断你的代码是否能够成功编译。
看到依赖问题,首先想到的就是把问题转化成「有向图」这种数据结构,只要图中存在环,那就说明存在循环依赖。
- 首先可以把课程看成「有向图」中的节点,节点编号分别是
0, 1, ..., numCourses-1
,把课程之间的依赖关系看做节点之间的有向边。- 比如说必须修完课程
1
才能去修课程3
,那么就有一条有向边从节点1
指向3
。
- 比如说必须修完课程
- 如果发现这幅有向图中存在环,那就说明课程之间存在循环依赖,肯定没办法全部上完;反之,如果没有环,那么肯定能上完全部课程。
- 用一个
hasCycle
变量记录是否存在环,onPath
记录一次 dfs 递归经过的节点 - 当重复遍历到
onPath
中的节点时,就说明遇到了环,设置hasCycle = true
。 - 用一个
visited
变量记录遍历过的节点,防止走回头路。- 假设以节点
2
为起点遍历所有可达的路径,最终发现没有环。 - 假设另一个节点
5
有一条指向2
的边,在以5
为起点遍历所有可达的路径时,肯定还会走到2
,此时就不需要继续遍历2
的所有可达路径了,避免了冗余计算
- 假设以节点
- 遍历图中的所有节点,通过是否有环即可判断能否修完所有课程。
代码
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {boolean}
*/
var canFinish = function (numCourses, prerequisites) {
// 图中共有 numCourses 个节点
let graph = new Array(numCourses).fill(0).map(() => []);
for (let [a, b] of prerequisites) {
// 在图中添加一条从 a 指向 b 的有向边
graph[a].push(b);
}
// 记录遍历过的节点,防止走回头路
let visited = new Array(numCourses).fill(false);
// 记录一次 dfs 递归经过的节点
onPath = new Array(numCourses).fill(false);
// 记录图中是否有环
hasCycle = false;
const dfs = (graph, i) => {
// 出现环
if (onPath[i]) {
hasCycle = true;
}
// 如果已经找到了环,或之前遍历过了没有环,就不用再遍历了
if (hasCycle || visited[i]) return;
// 前序代码位置
onPath[i] = true;
visited[i] = true;
for (let j of graph[i]) {
dfs(graph, j);
}
// 后序代码位置
onPath[i] = false;
};
// 遍历图中的所有节点
for (let i = 0; i < numCourses; i++) {
dfs(graph, i);
}
// 只要没有循环依赖可以完成所有课程
return !hasCycle;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
210 | 课程表 II | [✓] | 深度优先搜索 广度优先搜索 图 1+ | |
261 | 以图判树 🔒 | 深度优先搜索 广度优先搜索 并查集 1+ | ||
310 | 最小高度树 | 深度优先搜索 广度优先搜索 图 1+ | ||
630 | 课程表 III | 贪心 数组 排序 1+ | ||
2392 | 给定条件下构造矩阵 | 图 拓扑排序 数组 1+ |