有向无环图及其应用

拓扑排序。在用邻接表表示图时,对有n个顶点和e条弧的有向图而言时间复杂度为O(n+e)。一个有向图能被拓扑排序的充要条件就是它是一个有向无环图。拓扑序列唯一不能唯一确定有向图。

AOV网(Activity On Vertex)：用顶点表示活动，边表示活动的优先关系的有向图称为AOV网。AOV网中不允许有回路，这意味着某项活动以自己为先决条件。

拓扑有序序列：把AOV网络中各顶点按照它们相互之间的优先关系排列一个线性序列的过程。若vi是vj前驱，则vi一定在vj之前；对于没有优先关系的点，顺序任意。

拓扑排序：对AOV网络中顶点构造拓扑有序序列的过程。方法：

在有向图中选一个没有前驱的顶点且输出之
从图中删除该顶点和所有以它为尾的弧
重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止(此时说明图中有环）
采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路).深度优先搜索只要在其中记录下搜索的节点数n，当n大于图中节点数时退出，并可以得出有回路。若有回路，则拓扑排序访问不到图中所有的节点，所以也可以得出回路。广度优先搜索过程中如果访问到一个已经访问过的节点，可能是多个节点指向这个节点，不一定是存在环。

算法描述：

把邻接表中入度为0的顶点依此进栈
若栈不空，则
栈顶元素vj退栈并输出；
在邻接表中查找vj的直接后继vk，把vk的入度减1；若vk的入度为0则进栈
若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。
AOE网：带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。

一些定义：

事件的最早发生时间（ve(j)）：从源点到j结点的最长的路径。意味着事件最早能够发生的时间。
事件的最迟发生时间（vl(j)）：不影响工程的如期完工，事件j必须发生的时间。
活动ai由弧<j,k>表示，持续时间记为 dut<j,k>,则有:
活动的最早开始时间：e(i)=ve(j)
活动的最迟开始时间：l(i)=vl(k) - dut()
活动余量：l(i)-e(i)的差
关键活动：活动余量为0的活动
关键路径：从源点到汇点的最长的一条路径，或者全部由关键活动构成的路径。关键活动一定位于关键路径上。
关键活动组成了关键路径，关键路径是图中的最长路径，关键路径长度代表整个工期的最短完成时间，关键活动延期完成，必将导致关键路径长度增加，即整个工期的最短完成时间增加。关键路径并不唯一，当有多条关键路径存在时，其中一条关键路径上的关键活动时间缩短，只能导致本条关键路径变成非关键路径，而无法缩短整个工期，因为其他关键路径没有变化。任何一条关键路径上的关键活动变长了，都会使这条关键路径变成更长的关键路径，并且导致其他关键路径变成非关键路径（如果关键路径不唯一）。关键活动不按期完成就会影响整个工程的完成时间。所有的关键活动提前完成,那么整个工程才会提前完成。关键路径也不能任意缩短，一旦缩短到一定程度，该关键活动可能变成非关键活动了。