定义：在一个表示工程的有向图Φ用顶点表示活动，用弧表示活动之间的优先关系这样的有向图为顶点表示活动的网，我们成为AOV网（Activity On Vertex Network）,AOV网中的弧表示活动之间的某种約束关系AOV网中不存在回路（即无环的有向图）。

定义：设G(V,E)是一个具有n个顶点的有向图V中的顶点序列v1,v2,.....,vn，满足若从顶点vi到vj有一条路径则頂点vi必在vj之前。这样的顶点序列成为拓扑序列

拓扑排序其实就是对一个有向图构造拓扑序列的过程。

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

拓扑排序使用邻接表的数据结构。还用栈作为辅助数据结构用来存储处理过程中入度为0的顶点，目的是为了避免每次查找时都要去遍历邻接表找有没有入度为0的顶点

对一个具有n个顶点e条弧的AOV网来说，时间复杂度为O（n+e）.

定义：在一个表示工程的帶权有向图中用顶点表示事件，用弧表示活动用弧上的权值表示活动持续的时间，这种有向图的弧表示活动的网我们称为AOE网（Activity On Edge Network）.AOE网Φ没有入度的顶点称为始点或源点，没有出度的顶点叫做终点或汇点

AOV网和AOE网的不同：

它们都是用来对工程建模的，但它们还是有很大的區别主要体现在AOV网是顶点表示活动的网，它只描述了活动之间的约束关系而AOE网是用有向边表示活动，边上的权值表示活动持续的时间AOE网是建立在AOV网基础之上（活动之间约束关系没有矛盾），再来分析完成整个工程至少需要多少时间或者为缩短完成工程所需时间，应當加快那些活动等问题

路径各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大路径长度的路径叫做关键路径在关键路徑上的活动叫做关键活动。

（2）、事件的最晚发生时间ltv(lastest time of vertex):即顶点Vk的最晚发生时间也就是每个顶点对应事件最晚需要开始的时间，超出此时間将会延误整个工程

（4）、活动的最晚开始时间lte(lastest time of edge):即弧ak的最晚开始时间，也就是不推迟工期的最晚开始时间

AOE网也用邻接表结构，与AOV网邻接表不同的是AOE网的邻接表中增加了weight域，用来存储弧的权值

计算顶点Vk的最早发生时间etv[k]的公式是：

计算顶点Vk的最晚开始时间ltv[k]的公式：

ete表示活动<Vk,Vj>的最早开始时间，是针对弧来说的但只有此弧的弧尾顶点Vk的事件发生了，它才开始因此ete = etv[k];即以Vk为弧尾的弧（活动）的最早开始时间ete等于弧尾顶点Vk的最早开始时间etv[k]。

当ete与lte相等时此活动为关键活动。

求关键路径的算法时间复杂度为O（n+e）,n个顶点e条边的有向无环图

注意：囿向无环图的关键路径不一定只有一条，也可以有多条如果有多条关键路径，则单单提高一条关键路径上的关建活动的速度并不能导致整个工期的缩短而是必须是提高同时在几条关键路径上的活动的速度。