拓扑序列

拓扑序列是顶点活动网中将活动按发生的先后次序进行的一种排列。 拓扑排序，是对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

简介在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)。

设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,…,vn,满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在vj之前，则我们称这样的顶点序列为一个拓扑序列。1

相关简介**有向无环图****（Directed Acyclic Graph, DAG）是有向图的一种，字面意思的理解就是图中没有环。常常被用来表示事件之间的驱动依赖关系，管理任务之间的调度。
AOV网：**在每一个工程中，可以将工程分为若干个子工程，这些子工程称为活动。如果用图中的顶点表示活动，以有向图的弧表示活动之间的优先关系，这样的有向图称为AOV网，即顶点表示活动的网。在AOV网中，如果从顶点vi到顶点j之间存在一条路径，则顶点vi是顶点vj的前驱，顶点vj是顶点vi的后继。活动中的制约关系可以通过AOV网中的表示。 在AOV网中，不允许出现环，如果出现环就表示某个活动是自己的先决条件。因此需要对AOV网判断是否存在环，可以利用有向图的拓扑排序进行判断。

拓扑排序**：**拓扑排序是对一个有向图构造拓扑序列的过程。拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：
（1）每个顶点出现且只出现一次。
（2）若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

过程对于一个给定的有向图，得到其拓扑序列的步骤如下：
①从图中选择一个人度为0的顶点，并输出该顶点；
②从图中删除该顶点及其相关联的有向边，调整被删除有向边的终点的入度（人度减1）；
③重复①和②；
④直到所有顶点均被输出，拓扑序列完成；否则，无拓扑序列。
可以证明，任何一个无环的有向图一定有拓扑序列，有环的有向图则无拓扑序列。2

解释该排列满足：如果图中有一条从u到v的路径，则顶点v必须出现在顶点u之后。找出顶点活动网中的拓扑序列称“拓扑排序”。

应用拓扑排序既可用深度优先搜索，也可用广度优先搜索实现。

本词条内容贡献者为:

徐恒山 - 讲师 - 西北农林科技大学