查看“︁拓撲排序”︁的源代码

{{NoteTA
|G1 = IT
}}
在[[计算机科学]]领域，有向图的'''拓扑排序'''（{{lang-en|Topological sorting}}）或'''拓撲定序'''（{{lang-en|Topological ordering}}）是对其顶点的一种[[全序关系|线性]]排序，使得对于从顶点<math> u </math>到顶点<math> v </math>的每个[[有向边]]<math> uv </math>，<math> u </math>在排序中都在<math> v </math>之前。

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

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

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

在[[图论]]中，由一个[[有向无环图]]的顶点组成的序列，当且仅当满足下列条件时，才能称为该[[图 (数学)|图]]的一个拓扑排序：

#序列中包含每个顶点，且每个顶点只出现一次；
#若A在序列中排在B的前面，则在图中不存在从B到A的[[路径 (图论)|路径]]。

== 算法 ==
=== 卡恩算法===
卡恩于1962年提出了该算法
<ref name=Kahn>{{citation
 | last = Kahn | first = Arthur B.
 | title = Topological sorting of large networks
 | journal = Communications of the ACM
 | volume = 5 | issue = 11 | year = 1962 | pages = 558–562
 | doi = 10.1145/368996.369025| s2cid = 16728233| doi-access = free}}</ref>。简单来说，假设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永久标记
     在L的起始位置插入n（如L已有内容 后移它们以空出起始位置）

这种拓扑排序的方法被首次公开于Tarjan的著作中<ref name=Tarjan>{{citation
 | last = Tarjan | first = Robert E. | author-link = Robert Tarjan
 | title = Edge-disjoint spanning trees and depth-first search
 | journal = Acta Informatica | volume = 6 | issue = 2 | year = 1976 | pages = 171–185
 | doi = 10.1007/BF00268499| s2cid = 12044793 }}</ref>。

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

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

==参考资料==
<references/>

==外部链接==
* [https://xlinux.nist.gov/dads/HTML/topologicalSort.html NIST Dictionary of Algorithms and Data Structures: topological sort] {{Wayback|url=https://xlinux.nist.gov/dads/HTML/topologicalSort.html |date=20181013023157 }}
* {{MathWorld|urlname=TopologicalSort|title=TopologicalSort}}
{{排序算法}}
{{算法}}

[[Category:图论]]
[[Category:图算法]]
[[Category:排序算法]]
[[Category:带有伪代码示例的条目]]