拓扑排序
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在计算机科学领域,有向图的拓扑排序(英语:Topological sorting)或拓扑定序(英语:Topological ordering)是对其顶点的一种线性排序,使得对于从顶点到顶点的每个有向边,在排序中都在之前。
例如,图形的顶点可以表示要执行的任务,并且边可以表示一个任务必须在另一个任务之前执行的约束;在这个应用中,拓扑排序只是一个有效的任务顺序。
当且仅当图中没有定向环时(即有向无环图),才有可能进行拓扑排序。
任何有向无环图至少有一个拓扑排序。已知有算法可以在线性时间内,构建任何有向无环图的拓扑排序。
在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,才能称为该图的一个拓扑排序:
- 序列中包含每个顶点,且每个顶点只出现一次;
- 若A在序列中排在B的前面,则在图中不存在从B到A的路径。
算法
[编辑]卡恩算法
[编辑]卡恩于1962年提出了该算法 [1]。简单来说,假设L是存放结果的列表,先找到那些入度为零的节点,把这些节点放到L中,因为这些节点没有任何的父节点。然后把与这些节点相连的边从图中去掉,再寻找图中的入度为零的节点。对于新找到的这些入度为零的节点来说,他们的父节点已经都在L中了,所以也可以放入L。重复上述操作,直到找不到入度为零的节点。如果此时L中的元素个数和节点总数相同,说明排序完成;如果L中的元素个数和节点总数不同,说明原图中存在环,无法进行拓扑排序。
L ← 包含已排序的元素的列表,目前为空 S ← 入度为零的节点的集合 当 S 非空时: 将节点n从S移走 将n加到L尾部 选出任意起点为n的边e = (n,m),移除e。如m没有其它入边,则将m加入S。 重复上一步。 如图中有剩余的边则: return error (图中至少有一个环) 否则: return L (L为图的拓扑排序)
深度优先搜索
[编辑]另一种拓扑排序的方法运用了深度优先搜索。深度优先搜索以任意顺序循环遍历图中的每个节点。若搜索进行中碰到之前已经遇到的节点,或碰到叶节点,则中止算法。
L ← 一个空的 用来存放已排序的节点的列表 当图中存在未永久标记的节点时: 选出任何未永久标记的节点n visit(n) function visit(节点 n) 如n被永久标记: return 如n被临时标记: stop (不是定向无环图,至少有一个环) 将n临时标记 对于每一个以n为起点的边(n,m): visit(m) 去掉n的临时标记 将n永久标记 在L的起始位置插入n(如L已有内容 后移它们以空出起始位置)
这种拓扑排序的方法被首次公开于Tarjan的著作中[2]。
例子
[编辑]在某校的选课系统中,存在这样的规则:每门课可能有若干门先修课,如果要修读某一门课,则必须要先修读此课程所要求的先修课后才能修读。假设一个学生同时只能修读一门课程,那么,被选课系统允许的他修完他需要所有课程的顺序是一个拓扑序。
在这个例子中,每一门课程对应有向图中的一个顶点,每一个先修关系对应一条有向边(从先修课指向需要先修课的课)。
参考资料
[编辑]- ^ Kahn, Arthur B., Topological sorting of large networks, Communications of the ACM, 1962, 5 (11): 558–562, S2CID 16728233, doi:10.1145/368996.369025
- ^ Tarjan, Robert E., Edge-disjoint spanning trees and depth-first search, Acta Informatica, 1976, 6 (2): 171–185, S2CID 12044793, doi:10.1007/BF00268499
外部链接
[编辑]- NIST Dictionary of Algorithms and Data Structures: topological sort (页面存档备份,存于互联网档案馆)
- 埃里克·韦斯坦因. TopologicalSort. MathWorld.
|
|