AOV网------用顶点 表示活动 ，用弧 表示活动间优先关系 的有向图 称为顶点表示活动的网(Activity On Vertex network)，简称AOV网

AOV网中不允许有回路，这意味着某项活动以自己为先决条件 拓扑排序 ------把AOV网络中各顶点 按照它们相互之间的优先关系 排列成一个线性序列的过程

检测AOV网中是否存在环 方法：对有向图 构造其顶点 的拓扑有序序列 ，若网中所有顶点 都在 它的拓扑有序序列 中，则该AOV网必定不存在环。

拓扑排序算法

AOV网的拓扑序列不唯一

拓扑排序能够检测图中是否有环存在

图采用邻接表 存放；计算所有顶点的入度，存放于一维数组中；

算法：

AOE网:表示工程计划的有向图 ，其中，顶点表示事件 ，弧表示活动 ，弧上的权值表示完成一项活动需要的时间

AOE网中的某些活动可以并行 进行，完成工程的最短时间 是从开始顶点到完成顶点的最长路径长度 。路径长度最长 的路径为关键路径 。关键路径 上所有活动 都叫做关键活动。

求解关键路径和关键活动通过事件的最早、最迟发生时间、活动的最早、最迟发生时间完成。

只有在某顶点 代表的事件 发生后，从该顶点 发出去的弧 所代表的各项活动 才能开始

只有进入 某顶点的各条弧代表的活动 都已经结束，该顶点所代表的事件才能发生 (*)

使用一维数组ve[]来保存每一事件的最早发生时间。

事件 v i v_i vi的最早发生时间ve[i]是从开始顶点 v 1 v_1 v1到顶点 v i v_i vi的最长路径长度 。

从开始顶点 v 1 v_1 v1出发，令ve[1]=0，按拓扑有序 求其余各顶点 的最早发生时间ve[k]（2≤k≤n）

ve[k] = max{ve[j]+dut(): ∈S},dut()表示活动的所需的时间,其中S是以顶点v_k为弧头的所有弧的集合。

一维数组vl []保存每一事件允许的最晚发生时间

事件 v i v_i vi允许的最晚发生时间 vl[i]是在保证完成顶点 v n v_n vn在ve[n]时刻发生的前提下，事件 v i v_i vi允许发生的最晚时间 ，它等于ve[n]减去 v i v_i vi到 v n v_n vn的最长路径长 度。

从完成顶点 v n v_n vn出发，令vl[n]=ve[n]，按逆拓扑有序求其余各顶点的允许的最晚发生时间vl[i] (n-1≥i≥1) vl[i]=min{vl[k]-dut(): ∈S}其中S是以顶点vi为弧尾的所有弧的集合。

■ 一维数组e []保存每一活动的最早发生时间

■ 设活动 a i a_i ai用弧 < v j , v k > 表示，与 a i a_i ai相联系的权值 dut()用表示，则 a i a_i ai的可能的最早开始时间e[i]等于事件 v j v_j vj可能的最早发生时间ve[j]。

设活动 a i a_i ai用弧 < v j , v k > 表示，与 a i a_i ai相联系的权值dut()用表示，则活动 a i a_i ai允许的最晚开始时间l[i]等于事件 v k v_k vk允许的最晚发生时间vl[k]-dut()。

（1）关键路径上 所有的活动都是关键活动 。因此提前完成非关键活动并不能加快工程的速度。

（2）网络中的关键路径并不唯一，对于有几条关键路径的网来说，仅仅提高某一条关键路径上关键活动的速度，是不能缩短整个工程工期的，而必须同时提高几条关键路径上关键活动的速度。

所以，并不是网中任何一个关键活动的提前完成，整个工程都能提前完成。