数据结构—拓扑排序

问：什么是拓扑排序，有什么用，应用场景是什么？

首先搞清楚什么是AOV网，如果用DAG(有向无环图)来表示一个工程，用来表示活动Vi必须先于Vj进行的这样一种关系，我们把这种有向图称为顶点表示活动的网络，记作AOV网。

拓扑排序：有一个有向无环图的顶点组成的一个序列，必须满足如下条件：

①每个顶点都必须出现，且只能出现一次；

②如果顶点A在序列中的位置处在B的前面，那么在图中不存在由B到A的路径。

注意拓扑排序序列并不唯一，每个AOV网都可以有一个或者多个拓扑序列。

关于应用场景，凡是没有环，即没有回路的工程图或者流程图都可以应用到，序列体现出活动之间的优先关系。