LeetCode 207. 课程表
题目描述
你这个学期必须选修 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。这是不可能的。
解题过程循序渐进讲解
这个问题的核心是判断一个有向图是否存在环。我们可以把课程看作图中的节点，而先修条件 [ai, bi] 表示一条从 bi 指向 ai 的有向边。如果这个有向图中存在环，就意味着存在循环依赖（比如A需要B先修，B又需要A先修），那么就不可能完成所有课程；反之，如果图中无环（即是一个有向无环图，DAG），那么就可以完成。
一个非常高效的判断方法是 拓扑排序（Topological Sorting）。拓扑排序是针对有向无环图（DAG）的线性序列，该序列满足：对于图中的每一条有向边 u -> v，在序列中 u 都出现在 v 的前面。如果我们能成功为所有课程生成一个拓扑序列，就说明图中无环，可以完成所有课程。
我们将采用 Kahn算法 来实现拓扑排序，这个算法基于广度优先搜索（BFS）。
第一步：将问题建模为图
- 课程总数是
numCourses，所以图中有numCourses个节点（0 到 numCourses-1）。 - 每个先修条件
prerequisites[i] = [ai, bi]表示一条从bi指向ai的有向边。bi是前提，ai是后续。
第二步：计算每个节点的入度
- 入度：指指向该节点的边的数量。对于一门课程，它的入度就等于它有多少门直接的先修课程。
- 我们需要一个数组（或列表）
inDegree，长度为numCourses，来记录每门课程的入度。 - 初始化
inDegree所有元素为 0。 - 遍历
prerequisites数组：- 对于每一对
[ai, bi]，这意味着有一条边从bi指向ai。 - 因此，课程
ai的入度需要加 1 (inDegree[ai]++)。
- 对于每一对
第三步：初始化队列
- 我们需要一个队列（通常是FIFO队列，如
queue或deque），来存放当前所有入度为 0 的节点。 - 遍历
inDegree数组，将所有入度为 0 的课程节点加入队列。这些课程是“起点”，它们没有先修课程，可以立即开始学习。
第四步：执行BFS（拓扑排序的核心过程）
- 初始化一个计数器
count = 0，用于记录我们已经成功“学习”（从图中移除）的课程数量。 - 当队列不为空时，循环执行以下步骤：
a. 出队：从队列中取出一个节点（一门课程），我们称之为course。
b. 计数：将计数器count加 1，表示我们成功安排了这门课程。
c. 处理邻居：找到所有以course作为先修课程的后续课程。换句话说，找到所有从course出发的边所指向的节点。
* 我们需要一个数据结构（通常是邻接表adjacencyList）来快速实现这一步。adjacencyList[course]应该存储所有直接依赖于course的课程列表。
d. 更新入度：对于course的每一个后续课程nextCourse：
* 将nextCourse的入度减 1。因为这相当于我们学完了它的一个先修课程course。
* 判断：如果nextCourse的入度减为 0，说明它的所有先修课程都已被学完，它变成了新的“起点”。此时，将nextCourse加入队列。
第五步：判断结果
- 当BFS循环结束时，我们检查计数器
count。 - 如果
count等于课程总数numCourses，说明我们成功为所有课程找到了一个学习顺序（即完成了拓扑排序），图中不存在环，返回true。 - 如果
count小于numCourses，说明图中存在环。因为环上的所有节点都至少有一个先修课程在环内，导致它们的入度永远无法变为 0，也就永远不会被加入队列。因此，返回false。
关键点与示例推导（以示例2为例）
- 构建邻接表：为了方便找到每个节点的“后继”，我们通常在第一步同时构建一个邻接表。
- 示例：
numCourses = 2,prerequisites = [[1,0],[0,1]] - 边1：
0 -> 1(因为[1,0]表示学1需要先学0，即0是1的前提，边从0指向1) - 边2：
1 -> 0(因为[0,1]表示学0需要先学1，即1是0的前提，边从1指向0) - 邻接表：
adjacencyList[0] = [1],adjacencyList[1] = [0]
- 示例：
- 计算入度：
inDegree[0] = 1(因为有一条从1指向0的边)inDegree[1] = 1(因为有一条从0指向1的边)
- 初始化队列：初始入度为0的节点？没有。所以队列为空。
- 执行BFS：因为队列一开始就为空，BFS循环直接结束。
- 判断结果：
count初始为0，numCourses为2。0 != 2，返回false。这正确地判断出了存在环（0<->1），无法完成学习。
这个算法的时间复杂度是 O(V + E)，其中 V 是节点数（课程数 numCourses），E 是边数（先修条件数 prerequisites.length），非常高效。