AOV网（Activity On Vertex Network )

网：带权图。若在带权的有向图中，以顶点表示事件，以边（或者弧）表示活动，弧的权值表示活动的开销，则此带权有向图称为用边表示活动的网，简称：（AOV网（Activity On Vertex Network )。

关键路径

如果用AOV网表示一个工程，那么正常情况下工程只有一个开始点和一个结束点，因此AOV网中只有一个入度为0的点，称为源点；一个出度为0的点，称为汇点。 AOV网具有以下两个性质： 1、只有在某顶点所代表的事情发生后，从该顶点出发的弧所代表的活动才能开始。 2、只有在进入某顶点的各弧所代表的活动都已经结束时，该顶点所代表的事情才能发生。

由于AOV网中的某些活动可以并行进行，所以完成整个工程最短时间是从源点到汇点的最大路径长度。具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动。

一个无环的有向图称为有向无环图，在AOV网中不存在有向环（或者称有向回路）

对于给定的AOV网，首先判断网中是否存在环路，只有有向无环图才具有现实意义。检查AOV网中是否存在回路的方法就是拓扑排序。

拓扑排序后，会得到一个有向图的顶点序列。

拓扑排序的实现

1、从网中选择一个没有前驱的顶点（入度为0）并且输出它。 2、从网中删去该顶点，并且删去从该顶点发出的全部有向边 3、重复上述两步，直到剩余的网中不存在没有前驱的顶点为止。

此操作有两种结果： 一、网中全部顶点都被输出，这说明网中不存在有向回路； 二、网中顶点未被全部输出，剩余的顶点均有前驱顶点，这说明网中存在有向回路。

由上图可得到的拓扑序列为C2、C1、C4、C3、C5、C7、C6。当然，如果输出是选取的顶点不同，那么拓扑序列也就不唯一了。

show the code