拓扑序列

科技工作者之家  |   2020-11-17 17:18

拓扑序列是顶点活动网中将活动按发生的先后次序进行的一种排列。 拓扑排序,是对一个有向无环图(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之后。找出顶点活动网中的拓扑序列称“拓扑排序”。

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

本词条内容贡献者为:

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