拓撲排序 在计算机科学领域有向图的拓扑排序英語Topological sorting或拓撲定序英語Topological ordering是对其顶点的一种线性排序使得对于从顶点 u displaystyle u 到顶点 v displaystyle v 的每个有向边 u v displaystyle uv  u displaystyle u 在排序中都在 v displaystyle v 之前 例如图形的顶点可以表示要执行的任务并且边可以表示一个任务必须在另一个任务之前执行的约束在这个应用中拓扑排序只是一个有效的任务顺序 当且仅当图中没有定向环时即有向无环图才有可能进行拓扑排序 任何有向无环图至少有一个拓扑排序已知有算法可以在线性时间内构建任何有向无环图的拓扑排序 在图论中由一个有向无环图的顶点组成的序列当且仅当满足下列条件时才能称为该图的一个拓扑排序 序列中包含每个顶点且每个顶点只出现一次 若A在序列中排在B的前面则在图中不存在从B到A的路径