拓撲排序

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

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

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

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

参考资料[编辑]

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