210. 课程表 II

🟠   🔖  深度优先搜索 广度优先搜索 图 拓扑排序  🔗 力扣 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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]

Output: [0,1]

Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Output: [0,2,1,3]

Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.

So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

Input: numCourses = 1, prerequisites = []

Output: [0]

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• All the pairs [ai, bi] are distinct.

题目大意

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

解题思路

什么时候无法修完所有课程？当存在循环依赖的时候。

其实这种场景在现实生活中也十分常见，比如我们写代码 import 包也是一个例子，必须合理设计代码目录结构，否则会出现循环依赖，编译器会报错，所以编译器实际上也使用了类似算法来判断你的代码是否能够成功编译。

看到依赖问题，首先想到的就是把问题转化成「有向图」这种数据结构，只要图中存在环，那就说明存在循环依赖。

1. 构建图：

• 首先可以把课程看成「有向图」中的节点，节点编号分别是 0, 1, ..., numCourses-1，把课程之间的依赖关系看做节点之间的有向边。
• 比如说必须修完课程 1 才能去修课程 3，那么就在图中添加一条从节点 1 指向 3 的边。
• 如果发现这幅有向图中存在环，那就说明课程之间存在循环依赖，肯定没办法全部上完；反之，如果没有环，那么肯定能上完全部课程。

2. 使用 DFS 检测环路：

• 用一个 hasCycle 变量记录是否存在环，onPath 记录一次 DFS 递归经过的节点。
• 当重复遍历到 onPath 中的节点时，就说明遇到了环，设置 hasCycle = true。
• 用一个 visited 变量记录遍历过的节点，防止走回头路。
  • 假设以节点 2 为起点遍历所有可达的路径，最终发现没有环。
  • 假设另一个节点 5 有一条指向 2 的边，在以 5 为起点遍历所有可达的路径时，肯定还会走到 2，此时就不需要继续遍历 2 的所有可达路径了，避免了冗余计算
• 遍历图中的所有节点，通过是否有环即可判断能否修完所有课程。

3. 收集学习顺序：

• 用一个 path 变量记录最终的学习路径，在 DFS 的后序位置更新 path，如果没有环路，将当前课程添加到 path 中。

复杂度分析

• 时间复杂度：O(V + E)

  • 图的构建时间复杂度为 O(V + E)，其中 V 是课程数量，E 是先决条件的数量。
  • DFS 遍历每个节点和每条边，因此 DFS 的时间复杂度也是 O(V + E)。
  • 因此，总的时间复杂度为 O(V + E)。

• 空间复杂度：O(V + E)

  • 需要使用额外的空间来存储图、访问状态数组和路径数组，空间复杂度为 O(V + E)。
  • 额外的递归栈空间取决于课程的数量，最坏情况下为 O(V)。
  • 因此，总的空间复杂度为 O(V + E)。

代码

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function (numCourses, prerequisites) {
	let graph = new Array(numCourses).fill(0).map(() => []);
	for (let [a, b] of prerequisites) {
		graph[a].push(b);
	}

	let visited = new Array(numCourses).fill(false),
		onPath = new Array(numCourses).fill(false),
		path = [],
		hasCycle = false;

	const dfs = (graph, i) => {
		if (onPath[i]) {
			hasCycle = true;
		}
		if (hasCycle || visited[i]) {
			return;
		}
		visited[i] = true;
		onPath[i] = true;

		for (let j of graph[i]) {
			dfs(graph, j);
		}

		path.push(i);
		onPath[i] = false;
	};

	for (let i = 0; i < numCourses; i++) {
		dfs(graph, i);
	}

	return hasCycle ? [] : path;
};

相关题目

题号	标题	题解	标签	难度
207	课程表	[✓]	深度优先搜索 广度优先搜索 图 1+
269	火星词典 🔒		深度优先搜索 广度优先搜索 图 3+
310	最小高度树		深度优先搜索 广度优先搜索 图 1+
444	序列重建 🔒		图 拓扑排序 数组
630	课程表 III		贪心 数组 排序 1+
1136	并行课程 🔒		图 拓扑排序
2115	从给定原材料中找到所有可以做出的菜		图 拓扑排序 数组 2+
2392	给定条件下构造矩阵		图 拓扑排序 数组 1+
2459	通过移动项目到空白区域来排序数组 🔒		贪心 数组 排序