拓扑排序简介

图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列必须满足下面两个条件:
  • 每个顶点出现且只出现一次。
  • 若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。
注意:有向无环图(DAG)才有拓扑排序。拓扑排序有一个或多个结果。

拓扑排序的过程

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

图示

例题

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注