拓撲排序

在计算机科学领域，有向图的拓扑排序或拓撲定序是对其顶点的一种线性排序，使得对于从顶点${\displaystyle u}$到顶点${\displaystyle v}$的每个有向边${\displaystyle uv}$，${\displaystyle u}$在排序中都在${\displaystyle v}$之前。

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

当且仅当图中没有定向环时（即有向无环图），才有可能进行拓扑排序。

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

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，才能称为该图的一个拓扑排序（英語：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的起始 

例子

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

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

参考资料

外部链接

• NIST Dictionary of Algorithms and Data Structures: topological sort （页面存档备份，存于互联网档案馆）
• 埃里克·韦斯坦因. TopologicalSort. MathWorld.