一、课上练习

编程练习

1. 课程安排的可行性检查: L3371
2. 奖金: L3372

二、知识总结

✨ 核心思想

拓扑排序是针对有向无环图（Directed Acyclic Graph，简称 DAG）的顶点的一种排序方法，其目的是对图中所有顶点进行线性排序，使得对于任何一条有向边 u→v，顶点 u 都在顶点 v 之前。拓扑排序不是唯一的，一个图可能有多个合法的拓扑排序结果。

✨ 应用场景

拓扑排序通常用于处理具有依赖关系的任务规划问题，例如：

1. 任务调度：在构建系统或项目管理中，一些任务必须在其他任务完成后才能开始。
2. 课程规划：学生选课系统中，一些课程有先决条件，必须先完成某些课程才能选修其他课程。
3. 解析表达式：在编译器中，解析变量的声明依赖关系。

✨ Kahn 算法

Kahn 算法是一个迭代过程，它通过选择没有入边的顶点，然后移除该顶点及其所有出边来逐步构建拓扑排序。

算法步骤：

1. 统计所有顶点的入度（指向该顶点的边的数量）。
2. 将所有入度为 0 的顶点放入一个队列中。
3. 从队列中取出一个顶点，将其添加到排序结果中，然后减少其所有邻接点的入度。
4. 如果邻接点的入度变为 0，则将其加入队列。
5. 重复步骤 3 和 4，直到队列为空。
6. 如果排序结果中的顶点数量少于图中的顶点总数，则图中存在环，无法进行拓扑排序。

下面的代码演示了 Kahn 算法的实现方式：

✨ 执行示例

以下面这个有向图为例，追踪 Kahn 算法的完整执行过程：

图的边：5→2, 5→0, 4→0, 4→1, 2→3, 3→1
顶点：0, 1, 2, 3, 4, 5

第 1 步：计算所有顶点的入度

第 2 步：将入度为 0 的顶点加入队列

队列：[4, 5]，结果：[]

第 3 步：取出顶点 4，处理其邻接点

• 取出 4，结果：[4]
• 4→0：顶点 0 入度 2→1
• 4→1：顶点 1 入度 2→1
• 队列：[5]

第 4 步：取出顶点 5，处理其邻接点

• 取出 5，结果：[4, 5]
• 5→2：顶点 2 入度 1→0，加入队列
• 5→0：顶点 0 入度 1→0，加入队列
• 队列：[2, 0]

第 5 步：取出顶点 2，处理其邻接点

• 取出 2，结果：[4, 5, 2]
• 2→3：顶点 3 入度 1→0，加入队列
• 队列：[0, 3]

第 6 步：取出顶点 0

• 取出 0，结果：[4, 5, 2, 0]
• 顶点 0 没有出边
• 队列：[3]

第 7 步：取出顶点 3，处理其邻接点

• 取出 3，结果：[4, 5, 2, 0, 3]
• 3→1：顶点 1 入度 1→0，加入队列
• 队列：[1]

第 8 步：取出顶点 1

• 取出 1，结果：[4, 5, 2, 0, 3, 1]
• 队列为空，算法结束

最终拓扑排序结果：4 5 2 0 3 1

排序结果包含 6 个顶点，等于图的总顶点数，说明图中没有环。

✨ 解题步骤详解

例题：判断课程安排是否可行

某学校有 4 门课程（编号 0-3），课程之间的先修关系为：学习课程 1 前必须先学课程 0，学习课程 2 前必须先学课程 0，学习课程 3 前必须先学课程 1 和课程 2。

解题步骤：

1. 建图：根据先修关系建立有向图：0→1, 0→2, 1→3, 2→3
2. 计算入度：顶点 0 入度 0，顶点 1 入度 1，顶点 2 入度 1，顶点 3 入度 2
3. 执行 Kahn 算法：入度为 0 的顶点 0 入队 → 处理后顶点 1、2 入度变为 0 → 依次处理 → 最终取出全部 4 个顶点
4. 判断结果：排序结果包含 4 个顶点 = 总顶点数，说明课程安排可行

如果存在环（例如增加一条边 3→0），则算法执行过程中某些顶点的入度始终不会变为 0，最终排序结果的顶点数 < 总顶点数，说明课程安排存在循环依赖，不可行。

✨ 常见错误

1. 忘记初始化入度数组：入度数组必须在遍历所有边之后才能使用，不能边建图边做拓扑排序
2. 没有判断是否有环：拓扑排序结束后必须检查排序结果的顶点数是否等于总顶点数，否则无法检测出图中存在的环
3. 混淆入度和出度：拓扑排序关注的是入度（指向该顶点的边数），不是出度
4. 图的表示方式错误：边 u→v 表示 u 必须在 v 之前，建图时应从 u 指向 v，不要搞反方向
5. 对有环图强行排序：如果题目没有保证图是 DAG，必须加上环检测逻辑

✨ 基于 DFS 的方法

基于 DFS 的拓扑排序利用递归堆栈来实现反向的顶点线性排序。

算法步骤：

1. 对每一个未访问的节点执行 DFS。
2. 在 DFS 访问过程中，一旦从一个节点的所有可达节点递归返回，就将该节点放入栈中。
3. 最后的栈即为拓扑排序的结果，只需将其元素依次弹出。

下面的代码演示了基于 DFS 的拓扑排序实现方式：

三、课后练习

编程练习

1. 家族树: L3373