拓扑排序简介

拓扑排序（Topological Sort）是一种重要的图算法，用于对有向无环图（DAG, Directed Acyclic Graph）中的节点进行排序。拓扑排序的结果是一种线性序列，使得对于图中的任意一条有向边（u, v），顶点u都在顶点v之前。这种排序常用于任务调度、编译器依赖关系分析等领域。

拓扑排序的基本原理

拓扑排序的基本思想是通过深度优先搜索（DFS）或广度优先搜索（BFS）遍历图中的节点，并在遍历的过程中记录节点的访问状态和遍历顺序。对于DFS方法，通常使用一个栈来记录拓扑排序的结果；对于BFS方法，通常使用一个队列。

拓扑排序的算法步骤

以下是使用BFS实现拓扑排序的算法步骤：

1. 初始化：

   • 创建一个入度数组indegree[]，用于记录每个节点的入度。
   • 创建一个队列queue，用于存储入度为0的节点。