【拓扑排序算法】拓扑排序是一种用于对有向无环图（DAG）进行排序的算法，其核心思想是将图中的所有顶点按照依赖关系依次排列，使得每条边从排在前面的顶点指向排在后面的顶点。该算法在任务调度、依赖分析等领域有广泛应用。
一、拓扑排序的基本概念
| 术语 | 含义 |
| 有向无环图（DAG） | 图中没有环，且边具有方向性 |
| 拓扑排序 | 对DAG中的顶点按依赖顺序排列的一种线性序列 |
| 入度 | 指向当前顶点的边的数量 |
| 出度 | 当前顶点指向其他顶点的边的数量 |
二、拓扑排序的实现步骤
1. 统计每个顶点的入度：计算每个顶点有多少条边指向它。
2. 选择入度为0的顶点：这些顶点没有前置依赖，可以作为排序的起点。
3. 将该顶点加入结果列表，并将其出边所指向的顶点的入度减1。
4. 重复上述过程，直到所有顶点都被处理或无法继续处理（说明存在环）。
三、拓扑排序的典型应用场景
| 应用场景 | 说明 |
| 课程安排 | 在选课系统中，先修课程必须在后续课程之前完成 |
| 项目管理 | 任务之间有先后依赖关系，需合理安排执行顺序 |
| 编译器优化 | 确定代码中变量或函数的依赖关系 |
| 数据流处理 | 在数据流图中确定处理顺序以避免死锁 |
四、拓扑排序的算法实现（伪代码）
```plaintext
function topologicalSort(graph):
初始化一个队列，将所有入度为0的顶点加入队列
初始化一个空的结果列表
while 队列不为空:
取出队首顶点u
将u加入结果列表
for 每个u的邻接顶点v:
v的入度减1
if v的入度为0:
将v加入队列
if 结果列表包含所有顶点:
返回结果列表（合法拓扑序列）
else:
返回错误信息（图中存在环）
```
五、拓扑排序的特点与限制
| 特点 | 说明 |
| 仅适用于DAG | 若图中存在环，则无法进行拓扑排序 |
| 可能存在多个有效序列 | 根据选择入度为0顶点的顺序不同，结果可能不同 |
| 时间复杂度 | O(V + E)，其中V为顶点数，E为边数 |
| 空间复杂度 | O(V)（用于存储入度和结果列表） |
六、总结
拓扑排序是处理有向无环图中依赖关系的重要工具，能够帮助我们有效地安排任务顺序或识别潜在的冲突。通过维护顶点的入度并逐步移除无依赖节点，可以高效地生成符合逻辑的排序结果。在实际应用中，需要注意图的结构是否满足DAG条件，并根据具体需求选择合适的实现方式。