【拓扑排序算法】拓扑排序是一种用于对有向无环图（DAG）进行线性排序的算法。它主要用于解决任务之间的依赖关系问题，例如在项目管理、编译顺序安排以及课程安排等场景中非常常见。拓扑排序的核心思想是：在图中找到一个节点序列，使得对于每一条有向边 (u, v)，u 在序列中出现在 v 的前面。
一、拓扑排序的基本概念
| 概念 | 描述 |
| 有向无环图（DAG） | 图中没有环路，且边具有方向性 |
| 入度 | 节点指向它的边的数量 |
| 出度 | 节点发出的边的数量 |
| 拓扑序列 | 满足所有边的方向要求的节点排列 |
二、拓扑排序的实现方法
常见的拓扑排序算法主要有两种：
1. Kahn 算法（基于入度表）
2. 深度优先搜索（DFS）方法
以下是两种算法的对比总结：
| 方法 | 原理 | 时间复杂度 | 空间复杂度 | 是否需要修改原图 | 适用场景 |
| Kahn 算法 | 通过不断删除入度为0的节点来构建序列 | O(V + E) | O(V + E) | 否 | 适用于一般DAG，易于实现 |
| DFS方法 | 通过后序遍历的方式记录节点顺序 | O(V + E) | O(V) | 是（需要逆序） | 适用于递归实现，适合图结构较小的情况 |
三、Kahn 算法步骤（以图为例）
1. 计算每个节点的入度。
2. 将所有入度为0的节点加入队列。
3. 取出队列中的节点，将其加入拓扑序列。
4. 遍历该节点的所有邻接节点，将它们的入度减1。
5. 如果某个邻接节点的入度变为0，则将其加入队列。
6. 重复步骤3-5，直到队列为空。
7. 如果最终拓扑序列长度不等于节点总数，说明图中存在环。
四、DFS方法步骤（以图为例）
1. 对每个未访问的节点进行DFS遍历。
2. 在DFS过程中，先递归处理所有邻接节点。
3. 当所有邻接节点处理完成后，将当前节点加入结果栈。
4. 最终将栈中的节点倒序输出，即为拓扑序列。
5. 若在DFS过程中发现回边（即访问到已访问但未完成的节点），则说明图中存在环。
五、应用实例
| 场景 | 应用描述 |
| 课程安排 | 某些课程必须先修，拓扑排序可确定学习顺序 |
| 编译依赖 | 编译器根据文件间的依赖关系决定编译顺序 |
| 任务调度 | 多个任务之间存在先后依赖关系时，合理安排执行顺序 |
六、总结
拓扑排序是处理有向无环图的一种有效手段，能够帮助我们理解任务之间的依赖关系并生成合理的执行顺序。无论是使用Kahn算法还是DFS方法，其核心目标都是确保图中所有边的方向关系得到满足。在实际应用中，选择哪种算法取决于具体需求和图的规模。