我们会把施工过程、生产流程、软件开发、教学安排等都当成一个项目工程来对待，所有的工程都可分为若干个“活动”的子工程。例如图7-8-1是我这非专业人士绘制的一张电影制作流程图，现实中可能并不完全相同，但基本表达了一个工程和若干个活动的概念。在这些活动之间，通常会受到一定的条件约束，如其中某些活动必须在另一些活动完成之后才能开始。就像电影制作不可能在人员到位进驻场地时，导演还没有找到，也不可能在拍摄过程中，场地都没有。这都会导致荒谬的结果。因此这样的工程图，一定是无环的有向图。
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网（ActivityOn Vertex Network）。AOV网中的弧表示活动之间存在的某种制约关系。比如演职人员确定了，场地也联系好了，才可以开始进场拍摄。另外就是AOV网中不能存在回路。刚才已经举了例子，让某个活动的开始要以自己完成作为先决条件，显然是不可以的。
设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v 1 ，v 2 ，……，v n ，满足若从顶点v i 到v j 有一条路径，则在顶点序列中顶点v i 必在顶点v j 之前。则我们称这样的顶点序列为一个拓扑序列。
图7-8-1这样的AOV网的拓扑序列不止一条。序列v 0 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v10 v11 v 12 v 13 v 14 v 15 v 16 是一条拓扑序列，而v 0 v 1 v 4 v 3 v 2 v 7 v 6 v 5 v 8 v 10 v 9 v 12 v 11 v 14 v 13 v 15 v 16 也是一条拓扑序列。
所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环（回路）的AOV网；如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环（回路），不是AOV网。
一个不存在回路的AOV网，我们可以将它应用在各种各样的工程或项目的流程图中，满足各种应用场景的需要，所以实现拓扑排序的算法就很有价值了。
若有收获，就点个赞吧
0 人点赞
