1.有向无环图（DAG）
定义：若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph）。
步骤：
- 1.把各个操作树不重复地排成一排
- 2.标出各个运算符的生效顺序（先后顺序有点出入的无所谓）
- 3.按顺序加入运算符，注意“分层”
- 4.从低向上逐层检查同层的运算符是否可以合体
2.AOV网
定义：AOV网（Activity On Vertex NetWork，用顶点表示活动的网）：用DAG图（有向无环图）表示一个工程。顶点表示活动，有向边<Vi,Vj>表示活动Vi必须先于活动Vi进行。
3.拓扑排序
定义：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序
特征：
- 1.每个顶点出现且只出现一次
- 2.若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。
实现：
- 1.从AOV网中选择一个没有前驱（入度为0）的顶点并输出
- 2.从网中删除该顶点和所有以它为起点的有向边
- 3.重复1,2直到当前的AOV网为空或当前网中不存在无前驱的顶点为止
4.逆拓扑排序
定义：对一个AOV网，如果采用下列方式进行排序，则称为逆拓扑排序
- 1.从AOV网中选择一个没有后继（出度为0）的顶点并输出。
- 2.从网中删除该顶点和所有以它为终点的有向边。
- 3.重复1、2直到当前的AOV网为空。
5.AOE网
1.定义：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网（Activity On Edge NetWork）。
2.性质：
- 1.只有在某个顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
- 2.只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。
- 3.在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始。
- 4.在AOE网中仅有一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。
注：有些活动是可以并行进行的
3.关键路径
A.从源点到汇点的有向路径可能有多条，在所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。
B.完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。
- 1.活动ai的最早开始时间e(i)——指该活动弧的起点所表示的事件的最早发生时间。
- 2.活动ai的最迟开始时间l(i)——指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。
- 3.活动ai的时间余量d(i) = l(i) - e(i),表示在不增加完成整个工程所需总时间的情况下，活动ai可以拖延的时间，若一个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即l(i)=e(i)的活动ai是关键活动，由关键活动组成的路径就是关键路径。
4.求事件发生时间
- 1.求所有事件的最早发生时间ve()
- 按拓扑排序序列，依次求各个顶点的ve(k);
- ve(源点)=0
- ve(k)=Max{ve(j) + weight(vj,vk)},vj为vk的任意前驱
- 2.求所有事件的最迟发生时间vl()
- 按逆拓扑排序序列，依次求各个顶点的vl(k);
- vl(汇点) = ve(汇点)
- vl(k) = Min{vl(j) -Weight(vk,vj)},vj为vk的任意后继
