第8章｜图与并查集

Unit 07 · LeetCode #210 课程表 II

仅本次页面有效

U07

Topological OrderingZero Indegree → Choose → Append → Release → Validate Length

拓扑排序不只证明“能完成”，
还要交出一条完整合法顺序。

Unit 06 只比较处理数量；本单元把每次从零入度前沿中取出的课程写入 order。当前沿同时存在多门课程时，可以任选一门，因此同一张图可能产生多条正确答案。

检测到上次学习现场阶段、案例、零入度前沿、输出序列、代码槽位和迁移进度均可恢复。

LeetCode #210 · 课程表 II

共有 numCourses 门课程，编号为 0 到 numCourses - 1。prerequisites[i] = [a, b] 表示修读课程 a 前必须先完成课程 b。返回一条能够完成全部课程的顺序；若答案不唯一，可返回任意一条；若无法完成，返回空数组。

示例 1 numCourses = 2 prerequisites = [[1,0]] 输出：[0,1] 示例 2 numCourses = 4 prerequisites = [[1,0],[2,0],[3,1],[3,2]] 输出：[0,1,2,3] 或 [0,2,1,3]

约束与 Python 签名

1 ≤ numCourses ≤ 2000 0 ≤ prerequisites.length ≤ numCourses × (numCourses - 1) prerequisites[i].length == 2 0 ≤ a, b < numCourses a != b，所有课程对互不相同 class Solution: def findOrder(self, numCourses, prerequisites): ...

本实验采用 Kahn 算法。最终必须检查 len(order) == numCourses，否则环可能留下一个看似合理但不完整的前缀。

Zero-Indegree Frontier

当前所有先修要求均已解除、可以立刻修读的课程集合。

Topological Order

对每条边 u → v，u 在结果中必须早于 v。

Non-uniqueness

前沿中同时有多个节点时，选择不同节点可能产生不同但都合法的答案。

Length Validation

只有输出覆盖全部节点，才能排除依赖环和遗漏分量。

拓扑顺序实验步骤 1

第八章 Unit 07 · Skill 卡

输出拓扑序 = 正确建边 + 收集全部零入度节点 + 每次取出一个合法节点写入 order + 释放后继 + 用结果长度验证是否覆盖全图。前沿有多个节点表示存在局部自由度，而不是算法不确定。

ConnectionUnit 06 的 completed → Unit 07 的 order

Invariantorder 中每个节点已满足全部先修

Choice任意零入度节点均可成为下一项

Validationlen(order) == numCourses

Cycle Result无法覆盖全部节点时返回 []

Complexity时间 O(V+E)，空间 O(V+E)

完成后停留在当前页面

不会自动跳转。可以切换选择策略，比较不同合法拓扑序，或返回迁移轨迹继续观察。