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 course 0 you have to first take course 1.

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+