拓扑排序
拓扑排序(Topological sorting)要解决的问题是给一个有向无环图的所有节点排序。
比如学习大学课程中有:程序设计、算法语言、高等数学、离散数学、编译技术、普通物理、数据结构、数据库系统等。按照例子中的排课,当我们想要学习 数据结构 的时候,就必须先学会 离散数学 和 编译技术。当然还有一个更加前的课程 算法语言。
这些课程就相当于几个顶点 \(u\), 顶点之间的有向边 \((u,v)\) 就相当于学习课程的顺序。教务处安排这些课程,使得在逻辑关系符合的情况下排出课表,就是拓扑排序的过程。
在一个 DAG(有向无环图)中,我们将图中的顶点以线性方式进行排序,使得对于任何的顶点 \(u\) 到 \(v\) 的有向边 \((u,v)\), 都可以有 \(u\) 在 \(v\) 的前面。
还有给定一个 DAG,如果从 \(i\) 到 \(j\) 有边,则认为 \(j\) 依赖于 \(i\)。如果 \(i\) 到 \(j\) 有路径(i 可达 j),则称 \(j\) 间接依赖于 \(i\)。
拓扑排序的目标是将所有节点排序,使得排在前面的节点不能依赖于排在后面的节点。
构造拓扑序列步骤:
-
从图中选择一个入度为零的点;
-
输出该顶点,从图中删除此顶点及其所有的出边。
重复上面两步,直到所有顶点都输出,拓扑排序完成,或者图中不存在入度为零的点,此时说明图是有环图,拓扑排序无法完成,陷入死锁。
Kahn 算法
过程
初始状态下,集合 \(S\) 装着所有入度为 \(0\) 的点,\(L\) 是一个空列表。
每次从 \(S\) 中取出一个点 \(u\)(可以随便取)放入 \(L\), 然后将 \(u\) 的所有边 $(u, v_1), (u, v_2), (u, v_3) \cdots $删除。对于边 \((u, v)\),若将该边删除后点 \(v\) 的入度变为 \(0\),则将 \(v\) 放入 \(S\) 中。
不断重复以上过程,直到集合 \(S\) 为空。检查图中是否存在任何边,如果有,那么这个图一定有环路,否则返回 \(L\),\(L\) 中顶点的顺序就是构造拓扑序列的结果。
伪代码如下:
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is not empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
参考: