打开主菜单

计算机科学领域,有向图的拓扑排序是其顶点的线性排序,使得对于从顶点到顶点的每个有向边在排序中都在之前。

例如,图形的顶点可以表示要执行的任务,并且边可以表示一个任务必须在另一个任务之前执行的约束;在这个应用中,拓扑排序只是一个有效的任务顺序。

如果且仅当图形没有定向循环,即如果它是有向无环图(DAG),则拓扑排序是可能的。

任何DAG具有至少一个拓扑排序,并且已知这些算法用于在线性时间内构建任何DAG的拓扑排序。

图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该的一个拓扑排序(英語:Topological sorting):

  1. 每个顶点出现且只出现一次;
  2. 若A在序列中排在B的前面,则在图中不存在从B到A的路径

算法编辑

卡恩算法编辑

卡恩于1962年提出的算法。简单来说就是,假设L是存放结果的列表,先找到那些入度为零的节点,把这些节点放到L中,因为这些节点没有任何的父节点。然后把与这些节点相连的边从图中去掉,再寻找图中的入度为零的节点。对于新找到的这些入度为零的节点来说,他们的父节点已经都在L中了,所以也可以放入L。重复上述操作,直到找不到入度为零的节点。如果此时L中的元素个数和节点总数相同,说明排序完成;如果L中的元素个数和节点总数不同,说明原图中存在环,无法进行拓扑排序。

L ← 包含已排序的元素的空列表
S ← 没有进入边的节点(入度为零的节点)的集合
当 S 非空时:
    将节点n从S移走
    将n加到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
如 图有边 则:
    return error   (图至少有一个环)
否则: 
    return L   (以拓扑排序的顺序)

例子编辑

在某校的选课系统中,存在这样的规则:每门课可能有若干门先修课,如果要修读某一门课,则必须要先修读此课程所要求的先修课后才能修读。假设一个学生同时只能修读一门课程,那么,被选课系统允许的他修完他需要所有课程的顺序是一个拓扑序。

在这个例子中,每一门课程对应有向图中的一个顶点,每一个先修关系对应一条有向边(从先修课指向需要先修课的课)。

参考资料编辑