算法研究：AOV网与拓扑排序

算法研究：AOV网与拓扑排序2013-08-20 csdn Simba888888在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称之为AOV网（Activity on Vextex Network）。AOV网中的弧表示活动之间存在的某种制约关系，AOV网中不能存在回路，让某个活动的开始要以自己完成作为先决条件，显然是不可以的。

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

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在（回路）的AOV网；如果输出顶点少了，哪怕是少了一个，也说明这个网存在环路，不是AOV网。

对AOV网进行拓扑排序的基本思路是：从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

由于在拓扑排序的过程中，需要删除顶点，显然用邻接表的结构会更加方便，考虑到算法中始终要查找入度为0的顶点，我们可以在原来顶点表结点结构中，增加一个入度域in, 即入度的数字，上面所提到的删除以某个顶点为尾的弧的操作也是通过将某顶点的邻接点的in减去1，表示删除了中间连接的弧。

对于图7-8-2的第一幅图AOV网，可以得到如第二幅图的邻接表数据结构。