算法之拓扑排序
拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列必须满足下面两个条件:
- 每个顶点出现且只出现一次。
- 若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。
graph TD id1((1)) --> id2((2)) id1((1)) --> id4((4)) id2((2)) --> id4((4)) id4((4)) --> id3((3)) id2((2)) --> id3((3)) id4((4)) --> id5((5)) id3((3)) --> id5((5))
有向无环图(DAG)才有拓扑排序,非DAG图没有拓扑排序一说。
拓扑排序的算法步骤
一个 DAG 图,如何写出它的拓扑排序呢?
- 从 DAG 图中选择一个 没有前驱(即入度为0)的顶点并输出。
- 从图中删除该顶点和所有以它为起点的有向边。
- 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。因此,也可以通过拓扑排序来判断一个 DAG 图是否有环。
- step 1
graph TD subgraph one id1((1)) --> id2((2)) id1((1)) --> id4((4)) id2((2)) --> id4((4)) id4((4)) --> id3((3)) id2((2)) --> id3((3)) id4((4)) --> id5((5)) id3((3)) --> id5((5)) end id1((1))--> e1(输出1)
- step 2
graph TD subgraph one id2((2)) --> id4((4)) id4((4)) --> id3((3)) id2((2)) --> id3((3)) id4((4)) --> id5((5)) id3((3)) --> id5((5)) end id2((2))--> e1(输出2)
- step 3
graph TD subgraph one id4((4)) --> id3((3)) id4((4)) --> id5((5)) id3((3)) --> id5((5)) end id4((4))--> e1(输出4)
- step 4
graph TD subgraph one id3((3)) --> id5((5)) end id3((3))--> e1(输出3)
- step 5
graph TD subgraph one id5((5)) end id5((5))--> e1(输出5)
例子
拓扑排序通常用来”排序”具有依赖关系的任务。比如,如果用一个DAG图来表示一个工程,其中每个顶点表示工程中的一个任务,用有向边<A,B>
表示在做任务 B 之前必须先完成任务 A。故在这个工程中,任意两个任务要么具有确定的先后关系,要么是没有关系,绝对不存在互相矛盾的关系(即环路)。
1 | import java.util.ArrayList; |