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

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我 们称之为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网，可以得到如第二幅图的邻接表数 据结构。