拓撲排序

维基百科,自由的百科全书
跳转至: 导航搜索

计算机科学领域,有向图的拓扑排序或拓扑排序是其顶点的线性排序,使得对于从顶点到顶点的每个有向边在排序中都在之前。 例如,图形的顶点可以表示要执行的任务,并且边缘可以表示一个任务必须在另一个任务之前执行的约束; 在这个应用中,拓扑排序只是一个有效的任务顺序。 如果且仅当图形没有定向循环,即如果它是有向无环图DAG),则拓扑排序是可能的。 任何 DAG 具有至少一个拓扑排序,并且已知这些算法用于在线性时间内构建任何 DAG 的拓扑排序。

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

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

也可以定义为:拓扑排序是对有向无环图的顶点的一种排序,它使得如果存在一条从顶点A到顶点B的路径,那么在排序中B出现在A的后面[1]

参考资料[编辑]

  1. ^ 《数据结构与算法分析——Java语言描述》 (美)Mark Allen Weiss 著 冯舜玺 译 机械工业出版社 9.2 拓扑排序