拓扑排序（topological sort）是判定一幅有向图没有环，同时给出有向无环图（DAG）的拓扑序的算法。这种算法通常作为 DAG 动态规划（（链接未公开））的前置算法。

算法

思路

• 使用邻接表存图，同时预处理出所有节点的入度，新建一个容器（以队列为例），并标记出所有入度为 0 的点，将所有入度为 0 的点入队。使用一个列表记录拓扑序，令 m 为边数。
• 当数列非空时，进行循环：
  • 将队头 u 出队，并将 u 加入拓扑序列表末尾。
  • 遍历 u 的所有出边 (u, v)：
    • 删除此边，相当于令 v 的入度减一，同时令 m 减一。
    • 若 v 的入度为 0，将 v 入队。
• 循环结束后，检查是否还有未访问的边（即检查 m 是否等于 0），若 m 不等于 0 说明有环。

修改

以上算法的队列实际上可以替换成其他数据结构，例如栈、双端队列、甚至无序集合等。加入集合的条件是入度为 0，这保证了节点入边指向的点已经被访问过。

例如，如果每个节点都带有编号，求字典序最大的拓扑序，可以用优先队列代替队列。