含义

拓扑排序（Topological Sorting）是一个有向无环图(DAG，Directed Acyclic Graph) 的所有顶点的线性序列。且该序列必须满足如下两个条件：

  • 每个顶点出现且只出现一次
  • 若存在一条从顶点 A 到 B 的路径，那么在序列中顶点A出现在顶点B前面

步骤

  1. 从DAG图中选择一个没有前驱(即入度为0)的顶点并输出
  2. 从图中删除该顶点和所有以它为起点的有向边。
  3. 重复1和2，直到当前的 DAG 图为空，或者当前图中不存在无前驱的顶点为止，后一种情况说明有向图中必定存在环。

例子

于是得到拓扑排序后的结果是 A,D,B,C,E。

通常，一个有向无环图可以有一个或多个拓扑排序序列。