esc to dismiss

拓扑排序

在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列必须满足下面两个条件:

  1. 每个顶点出现且只出现一次。

  2. 若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。

写出拓扑排序的常用算法为 Kahn 算法,简单而言就是:

  1. 计算每个顶点的入度(即有几个顶点指向它)。

  2. 将入度为0的顶点取出,取出后更新其指向顶点的入度,再依次取出更新后的入度为0的顶点,这样依次类推,取出的序列即为拓扑排序序列。

x