拓扑排序
含义
拓扑排序(Topological Sorting)是一个有向无环图(DAG,Directed Acyclic Graph) 的所有顶点的线性序列。且该序列必须满足如下两个条件:
- 每个顶点出现且只出现一次
- 若存在一条从顶点 A 到 B 的路径,那么在序列中顶点A出现在顶点B前面
步骤
- 从DAG图中选择一个没有前驱(即入度为0)的顶点并输出
- 从图中删除该顶点和所有以它为起点的有向边。
- 重复1和2,直到当前的 DAG 图为空,或者当前图中不存在无前驱的顶点为止,后一种情况说明有向图中必定存在环。
于是得到拓扑排序后的结果是 A,D,B,C,E。
通常,一个有向无环图可以有一个或多个拓扑排序序列。