For faster navigation, this Iframe is preloading the Wikiwand page for 拓扑排序.

拓扑排序

维基百科,自由的百科全书

此条目没有列出任何参考或来源。 (2019年5月1日)维基百科所有的内容都应该可供查证。请协助补充可靠来源改善这篇条目无法查证的内容可能会因为异议提出而移除。

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

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

当且仅当图中没有定向环时(即有向无环图),才有可能进行拓扑排序。

任何有向无环图至少有一个拓扑排序。已知有算法可以在线性时间内,构建任何有向无环图的拓扑排序。

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

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

算法

卡恩算法

卡恩于1962年提出了该算法。简单来说,假设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永久标记
    将n加到L的起始

例子

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

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

参考资料


外部链接

{{bottomLinkPreText}} {{bottomLinkText}}
拓扑排序
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.