0207. Course Schedule
=====================
题目信息
--------
:题号: 0207. 课程表
:难度: Medium
:主题: 有向图、拓扑排序、环检测
:原题: `LeetCode 0207 `_
:重点: 将先修关系定向为先修课到后续课,只有无环图才能逐步取出零入度课程
题目重述
--------
共有 ``numCourses`` 门课程,编号为 ``0`` 到 ``numCourses - 1``。每个先修关系
``[course, prerequisite]`` 表示必须先完成 ``prerequisite``,才能学习 ``course``。判断是否
存在一种顺序完成全部课程;能完成返回 ``true``,否则返回 ``false``。
``numCourses`` 位于 ``[1, 2000]``,先修关系数量不超过 ``5000``,课程编号均合法,关系对互不
重复。课程图可以有多个互不相连的分量,也可以有完全没有先修关系的孤立课程;函数只判断可行性,
不需要返回具体顺序。
自建示例
--------
分支最终汇合:
.. code-block:: text
输入:numCourses = 4,prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出:true
解释:先完成 0,再完成 1、2,最后完成 3。
局部循环会阻塞全部课程:
.. code-block:: text
输入:numCourses = 4,prerequisites = [[1,0],[0,1]]
输出:false
解释:0 和 1 互相等待;即使课程 2、3 没有先修关系,也不能完成全部课程。
没有任何先修关系:
.. code-block:: text
输入:numCourses = 3,prerequisites = []
输出:true
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
public:
bool canFinish(int numCourses,
std::vector>& prerequisites) {
return canFinishByIndegree(numCourses, prerequisites);
}
private:
bool canFinishByIndegree(int numCourses,
const std::vector>& prerequisites) {
std::vector> graph(numCourses);
std::vector indegree(numCourses, 0);
for (const auto& prerequisite : prerequisites) {
int course = prerequisite[0];
int prerequisiteCourse = prerequisite[1];
graph[prerequisiteCourse].push_back(course);
++indegree[course];
}
std::queue ready;
for (int course = 0; course < numCourses; ++course) {
if (indegree[course] == 0) ready.push(course);
}
int processed = 0;
while (!ready.empty()) {
int course = ready.front();
ready.pop();
++processed;
for (int next : graph[course]) {
if (--indegree[next] == 0) ready.push(next);
}
}
return processed == numCourses;
}
bool canFinishByDfs(int numCourses,
const std::vector>& prerequisites) {
std::vector> graph(numCourses);
for (const auto& prerequisite : prerequisites) {
graph[prerequisite[1]].push_back(prerequisite[0]);
}
std::vector state(numCourses, 0);
for (int course = 0; course < numCourses; ++course) {
if (state[course] == 0 && hasCycle(course, graph, state)) {
return false;
}
}
return true;
}
bool hasCycle(int course,
const std::vector>& graph,
std::vector& state) {
state[course] = 1;
for (int next : graph[course]) {
if (state[next] == 1) return true;
if (state[next] == 0 && hasCycle(next, graph, state)) return true;
}
state[course] = 2;
return false;
}
};
题解
----
先修关系就是有向边
~~~~~~~~~~~~~~~~~~~~
把 ``[course, prerequisite]`` 直接理解成 ``course -> prerequisite`` 容易把方向写反。为了表示
“先完成谁”,统一建立边:
.. code-block:: text
prerequisite -> course
这样,一个课程的入度就是它尚未完成的直接先修课程数量。完成全部课程等价于找到一个拓扑顺序:
每条边的起点都出现在终点之前。
暴力排列与局部选择
~~~~~~~~~~~~~~~~~~~~
枚举所有课程排列并逐条检查先修关系是阶乘级搜索。更有希望的贪心是每一步选择当前没有未完成
先修课的课程,完成它后再释放后续课程;因为它当前入度为 0,把它接到已有顺序末尾不会违反
任何边。
若某一步没有可选课程,却仍有课程未完成,剩余课程之间的每个入度都大于 0。沿剩余入边不断
回溯,有限节点中必然重复,形成环;环内没有第一个可以启动的课程。因此“能否持续取出零入度
课程直到全部完成”正好等价于“图是否无环”。
Kahn 算法逐步删除已完成课程
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
``canFinishByIndegree`` 维护两类状态:邻接表保存每门课程完成后会释放哪些后续课程,
``indegree`` 保存仍来自未完成课程的边数。初始化时把所有入度为 0 的课程放入队列。
每弹出课程 ``course``,就把它视为已完成,并遍历所有 ``course -> next`` 边,将
``indegree[next]`` 减一;某个后继第一次变为 0 时,说明它的全部先修课都已经完成,可以入队。
每门课程只会从 1 变为 0 一次,因此不会重复入队。
核心不变量
~~~~~~~~~~~~
每轮开始时保持:
* 对任何未完成课程,``indegree`` 恰好是它来自未完成课程的剩余入边数量;
* 队列中的课程恰好是已发现、未处理且当前入度为 0 的课程;
* 已处理课程的顺序满足所有已经删除的边;
* 每条邻接边只在其起点被处理时删除一次,入度与边的数量同步。
处理零入度课程不会制造新的前置违反;递减后继入度只删除一条已经满足的先修边,所以不变量
可以逐轮推进。最终 ``processed == numCourses`` 时,出队顺序就是合法拓扑序;否则队列先空,
剩余图含有环。
状态走读
~~~~~~~~
对 ``[[1,0],[2,0],[3,1],[3,2]]``,边为 ``0->1、0->2、1->3、2->3``:
.. list-table::
:header-rows: 1
* - 阶段
- 队列
- 入度
- processed
* - 初始化
- ``[0]``
- ``[0,1,1,2]``
- 0
* - 处理 0
- ``[1,2]``
- ``[0,0,0,2]``
- 1
* - 处理 1
- ``[2]``
- ``[0,0,0,1]``
- 2
* - 处理 2
- ``[3]``
- ``[0,0,0,0]``
- 3
* - 处理 3
- ``[]``
- ``[0,0,0,0]``
- 4
课程 3 要等 1、2 两条入边都删除后才入队。若只有 ``0->1``、``1->0``,初始化入度为
``[1,1]``,队列为空,``processed`` 保持 0,算法立即判定无法完成全部课程。
DFS 三色判环
~~~~~~~~~~~~~~
``canFinishByDfs`` 用另一种状态压缩表达同一结论:0 表示未访问,1 表示正在当前递归路径中,
2 表示该课程及其后继已经确认无环。沿边访问时遇到状态 1,就是从当前路径回到了祖先,形成
有向环;完成全部后继后标为 2,可被其他分量复用而不重复搜索。
DFS 与 Kahn 都是 ``O(V+E)``,但递归深度可能达到课程数;主入口选择 Kahn,使用显式队列并让
处理数量直接对应“已完成课程数”。外层遍历所有课程仍然必要,因为图可能有多个不连通分量。
代码分析
~~~~~~~~
建图时必须把 ``prerequisite[1]`` 放在邻接表起点,把 ``prerequisite[0]`` 作为后继;入度只
增加后者。队列初始化覆盖所有孤立课程和所有分量的入口,不能只从课程 0 开始搜索。
弹出课程后先增加 ``processed``,再遍历邻接项递减入度。边被访问一次且只在从 1 变成 0 时入队,
所以队列不会重复同一课程;最后比较数量而不是只检查队列是否为空,才能发现局部环留下的未处理
课程。
DFS 版本的 ``state`` 只记录“当前递归路径”和“已完成搜索”两种有区别的访问状态;若把访问过
的节点简单标成一个布尔值,会丢失回边与跨分支边的语义,可能漏报环。
复杂度与边界
~~~~~~~~~~~~
设课程数为 ``V``、先修关系数为 ``E``。Kahn 建图、入度处理和队列遍历总时间为 ``O(V+E)``,
邻接表、入度数组和队列额外空间为 ``O(V+E)``;DFS 同阶,但递归栈最坏为 ``O(V)``。
没有先修关系时所有课程初始入队,返回 ``true``;孤立课程与其他分量独立处理。自环或更长环
不会产生零入度入口,最终使处理数量小于 ``V``。输入关系保证课程编号和二元结构合法,代码不需
额外修复无效边。