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