拓扑排序 #

定义 #

有向无环图(DAG, Directed Acyclic Graph)指的是一个无回路的有向图. 拓扑排序(Topological Sorting)是一个有向无环图里所有顶点的线性序列, 且该序列满足下面两个条件:

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

Kahn 算法 #

对于有向图 $G = (V, E)$ , 定义 $S$ 为 $G$ 中所有入度为 $0$ 的顶点构成的集合, $L$ 是一个空列表. 每次从 $S$ 中取出一个顶点 $u$ 放入 $L$ , 然后将 $u$ 的所有边 $(u, v_1), (u, v_2), …, (u, v_m)$ 删除. 对于边 $(u, v)$ , 如果删除之后 $v$ 的入度变为 $0$ , 则把 $v$ 加入到 $S$ 中. 不断重复上述操作, 直到集合 $S$ 为空. 检查 $G$ 中是否剩下任何边. 如果有, 那么 $G$ 一定存在环路, 无法进行拓扑排序; 否则返回 $L$ , $L$ 中顶点的顺序就是拓扑排序的结果. Kahn 算法的时间复杂度是 $O(E+V)$ .