DAG and its Applications
介绍
一个无环的有向图称作有向无环图(directed acycline graph)，简称DAG图。DAG图是较有向树更一般的特殊有向图。
有向无环图是描述含有公共子式的表达式的有效工具。
利用DAG图，可实现对相同子式的共享，从而节省存储空间。下面是一个例子：
检查有向图是否存在环
检查一个有向图是否存在环比无向图复杂的多。对于无向图，若深度优先遍历过程中遇到回边(即指向已访问过的顶点的边)，则必存在环。而对于有向图而言，而这条边可能是指向深度优先生成森林中另一棵生成树上顶点的弧。
如果从有向图上某个顶点v出发的遍历，在dfs(v)结束之前出现一条从顶点u到顶点v的回边，由于u在生成树上是v的子孙，则该有向图中必定存在包含顶点v和u的环。
有向无环图也是描述一项工程或系统的进行过程的有效工具。除最简单的情况之外，几乎所有的工程(project)都可以分为若干个称作活动(activity)的子工程，而这些工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。
对整个工程和系统，人们关心的是两个方面的问题：一是工程是否能顺利进行；二是估算整个工程完成所必需的最短时间。对应于有向图，即为进行拓扑排序和求关键路径的操作。下面将详细介绍。
拓扑排序
拓扑排序(Topological Sort)
由某个集合上的一个偏序得到该集合山的一个全序，这个操作称之为拓扑排序。
下面是离散数学中对于偏序和全序的定义：
- 若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系；
- 设R是集合X上的偏序(Partial Order)，如果对每个x,y属于X，必有
xRy或者yRx，则称R是集合X上的全序关系。
下面是一个直观例子。
直观的看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。
一个表示偏序的有向图可用来表示一个流程图。图中每一条有向边表示两个子工程之间的次序关系(领先关系)。
AOV-网
【AOV-网】用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network)。
在AOV-网中，若从顶点i到顶点j有一条有向路径(一条或多条弧组成)，则i是j的前驱，j是i的后继。若<i,j>是网中的一条弧，则i是j的直接前驱直接后继，j是i的直接后继。
AOV-网中，不应该出现有向环（存在着环意味着"某项活动应以自己为先决条件"，这对程序的流程图来说，则表示存在着一个死循环）。
【判断AOV-网中是否存在环】对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV-网中必定不存在环。
【如何拓扑排序】
-
- 在有向图中选一个没有前驱的顶点且输出之；
-
- 从图中删除该顶点和所有以它为尾的弧。
- 重复上面两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况说明有向图中存在环。
计算机中如何实现拓扑排序？ 针对上面两步操作，我们采用邻接表作为有向图的存储结构，且在头结点中增加一个存放顶点入度的数组(indegree)。入度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧的操作，则可通过弧头顶点的入度减1来实现。为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点，由此可得拓扑排序的算法。【见文末附录】
拓扑排序算法的时空复杂度
对有n个顶点和e条弧的有向图而言，建立求各顶点入度的时间复杂度为O(e)；建零入度点点栈的时间复杂度为O(n)；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈，出一次栈，入度减1的操作在WHILE语句中共执行e次，所以，总的时间复杂度为O(n+e)。
使用dfs拓扑排序无环有向图
dfs进行拓扑排序仅适用于有向图无环的情况。
因为图中无环，则由图中某点出发进行深度有先搜索遍历时，最先退出DFS函数的顶点即出度为零的顶点，是拓扑有序序列中最后一个顶点。
由此，按退出DFS函数先后记录下来的顶点序列，即为逆向的拓扑有序序列。
关键路径
【AOE-网】与AOV-网相对应，即边表示活动的网(Activity On Edge)。
AOE-网是一个带权的有向无环图(DAG)，其中，顶点表示事件(Event)，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。
【路径长度】路径上各活动持续时间之和。
由于在AOE-网中有些活动可以并行地进行，所以完成工程地最短时间是从开始点到完成点地最长路径长度。
【关键路径】路径长度最长的路径。
我们用e(i)表示活动a_i的最早开始时间，用l(i)表示活动a_i最迟必须开始的时间，两者之差为l(i)-e(i)意味着完成活动a_i的时间余量。
【关键活动】l(i) = e(i)的活动。显然，关键路径上的所有活动都是关键活动（因此，提前完成非关键活动并不能加快工程的进度）。
【分析关键路径的目的】辨别哪些是关键活动，以便争取提高关键活动的工效，缩短整个工期。
【求关键路径的算法】
- 输入
e条弧<j,k>，建立AOE-网的存储结构； - 从源点
v0出发，令ve[0] = 0，按拓扑有序求其余各顶点的最早发生时间ve[i]，1<=i<=n-1。如果得到的拓扑有序中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤3. - 从汇点vn出发，令
vl[n-1] = ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i], n-2>=i>=2; - 根据各点顶点的
ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s) = l(s)，则为关键活动。
由于拓扑排序必定在网中无环的前提下，则也可以利用DFS函数，在退出DFS函数之前计算顶点v的vl值（因为此时v的所有直接后继的vl值都已求出）。
上述两种算法的时间复杂度均为O(n+e)，显然，前一种算法(非dfs)的常数因子要小些。由于计算弧的活动最早开始时间和最迟开始时间的复杂度为O(e)，所以总的求关键路径的时间复杂度为O(n+e)。
下面是关键路径求解实例.
附录
拓扑排序的算法
Status TopologicalSort(ALGraph G) {
// 有向图G采用邻接表存储结构
// 若G无回路，则输出G的顶点的一个拓扑排序并返回OK，否则ERROR
FindInDegree(G, indegree); // 对各顶点求入度indegree[0...vernum-1]
InitStack(S);
for(i = 0; i < G.vexnum; ++i) // 建零入度顶点栈S
if(!indegree[i]) Push(S, i); // 入度为0者入栈
count = 0; // 对输出顶点计数
while(!StackEmpty(S)) {
Pop(S, i); printf(i, G.vertices[i].data); ++count; // 输出i号顶点并计数
for(p = G.vertices[i].firstarc; p; p = p->nextarc) {
k = p->adjvex; // 对i号顶点的每个邻接点的入度减1
if(!(--indegree[k])) Push(S, k); // 若入度为0，则入栈
} // for
} // while
if(count < G.vexnum) return ERROR; // 该有向图有回路
else return OK;
}