有向无环图及其应用
本章我们介绍一下有向无环图及其相关的应用。
1. 有向无环图
一个无环的有向图称作有向无环图(directed acycline graph)，简称DAG图。DAG图是一类较有向树更一般的特殊有向图，如下图7.21列示了有向树、DAG图和有向图的例子。
有向无环图是描述含有公共子式的表达式的有效工具。例如下述表达式：
((a+b) * (b * (c+d)) + (c+d)*e) * ((c+d)*e)
可以用第6章讨论的二叉树来表示，如下图7.22所示。仔细观察该表达式，可发现有一些相同的子表达式，如(c+d)和(c+d)*e等，在二叉树中，它们也重复出现。若利用有向无环图，则可以实现对相同子式的共享，从而节省存储空间。例如下图7.23所示为表示同一表达式的有向无环图。
检查一个有向图是否存在环要比无向图复杂。对于无向图来说，若深度优先遍历过程中遇到回边（即指向已访问过的顶点的边），则必定存在环；而对于有向图来说，这条回边有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。但是，如果从有向图上某个顶点v出发出发的遍历，在dfs(v)结束之前出现一条从顶点u到顶点v的回边（如图7.24所示），由于u在生成树上是v的子孙，则有向图中必定存在包含顶点v和u的环。
有向无环图也是描述一项工程或系统的进行过程的有效工具。除最简单的情况之外，几乎所有的工程(project)都可分为若干个称作活动(activity)的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。对整个工程和系统，人们关心的是两个方面的问题： 一是工程能否顺利进行；二是估算整个工程完成所必须的最短时间，对应于有向图，即为进行拓扑排序和求关键路径的操作。下面分别就这两个问题讨论之。
1.1 拓扑排序
什么是拓扑排序(Topological Sort)?简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。回顾离散数学中关于偏序和全序的定义：
若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。
直观地看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。例如，下图7.25所示的两个有向图，图中弧<x,y> 表示x<=y，则(a)表示偏序，(b)表示全序。若在(a)的有向图上人为地加一个表示v2<=v3的弧(符号<=表示v2领先于v3)，则(a)表示的亦为全序，且这个全序称为拓扑有序(Topological Order)，而由偏序定义得到的拓扑有序的操作便是拓扑排序。
一个表示偏序的有向图可用来表示一个流程图。它或者是一个施工流程图，或者是一个产品生产的流程图，再或者是一个数据流图（每个顶点表示一个过程）。图中每一条有向边表示两个子工程之间的次序关系（领先关系）。
例如，一个软件专业的学生必须学习一系列基本课程（如下图7.26所示），
其中有些课程是基础课，它独立于其他课程，如《高等数学》；而另一些课程必须在学完作为它的基础的先修课程才能开始。如，在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先（优先）关系。这个关系可以用有向图更清楚地表示，如图7.27所示。图中顶点表示课程，有向边（弧）表示先决条件。若课程i是课程j的先决条件，则图中有弧<i,j>。
这种用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network)，简称AOV-网。在网中，若从顶点i到顶点j有一条有向路径，则i是j的前驱；j是i的后继。若<i,j>是网中的一条弧，则i是j的直接前驱；j是i的直接后继。
在AOV-网中，不应该出现有向环，因为存在环意味着某项活动应以自己为先决条件。显然，这是荒谬的。若设计出这样的流程图，工程便无法进行。而对程序的流程图来说，则表明存在一个死循环。因此，对给定的AOV-网应首先判定网中是否存在环。检测的办法是对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，在该AOV-网中必定不存在环。例如，图7.27的有向图有如下两个拓扑有序序列：
(C1, C2, C3, C4, C5, C7, C9, C10, C11, C6, C12, C8) 和 (C9, C10, C11, C6, C1, C12, C4, C2, C3, C5, C7, C8)
(当然，对此图也可构造得其他的拓扑有序序列）。若某个学生每学期只学一门课程的话，则他必须按拓扑有序的顺序来安排学习计划。
如何进行拓扑排序？解决的方法很简单：
1） 在有向图中选一个没有前驱的顶点且输出之；
2） 从图中删除该顶点和所有以它为尾的弧；
重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。
以图7.28(a)中的有向图为例，图中，v1和v6没有前驱，则可任选一个。假设先输出v6，在删除v6及弧<v6,v4>，<v6, v5>之后，只有顶点v1没有前驱，则输出v1且删去v1及弧<v1,v2>、<v1,v3>和<v1,v4>，之后v3和v4都没有前驱。依次类推，可从中任选一个继续进行。整个拓扑排序的过程如图7.28所示。最后得到该有向图的拓扑有序序列为：
v6-v1-v4-v3-v2-v5
如何在计算机中实现呢？针对上述两步操作，我们可采用邻接表做有向图的存储结构，且在头节点中增加一个存放顶点入度的数组(indegree)。入度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧的操作，则可换以弧头顶点的入度减一来实现。
为了避免重复检测入度为0的顶点，则可设一栈(stack)来暂存所有入度为零的顶点，由此可得拓扑排序的算法如7.12所示。
算法7.12
Status TopologicalSort(ALGraph G)
{
//有向图采用邻接表存储结构
//若无回路，则输出G的顶点的一个拓扑序列并返回OK，否则ERROR
FindInDegree(G, indegree); //对各顶点求入度 indegree[0..vernum-1]
InitStack(S); //建零入度顶点栈S
for(i = 0; i<G.vexnum; i++){
if(!indegree[i])
Push(S, i); //入度为0者进栈
}
count = 0; //对输出顶点的个数进行计数
while(!StackEmpty(S)){
Pop(S, i);
printf(i, G.vertices[i].data);
count++;
for(p = G.vertices[i].firstarc; p; p = p->nextarc){
k = p->adjvex; //对i号顶点的每个邻接点的入度减1
if(!(--indegree[k])) //若入度为0，则入栈
Push(S, k);
}
}
if(count < G.vexnum) //该有向图有回路
return ERROR;
else
return OK;
}分析算法7.12，对有n个顶点和e条弧的有向图而言，建立求各顶点入度的时间复杂度为O(e)；建零入度顶点栈的时间复杂度为O(n)；在拓扑排序过程中，若有向图无环，每个顶点进一次栈，出一次栈，入度减1的操作在while语句中总共执行e次，所以，总的时间复杂度为O(n+e)。上述拓扑排序的算法亦是下节讨论的求关键路径的基础。
当有向图中无环时，也可利用深度优先遍历进行拓扑排序。因为图中无环，则由图中某点出发进行深度优先遍历时，最先退出DFS函数的顶点即出度为零的顶点，是拓扑有序序列中最后一个顶点。由此，按退出DFS函数的先后记录下来的顶点序列（如同求强连通分量时finished数组中的顶点序列）即为逆向的拓扑有序序列。
1.2 关键路径
与AOV-网相对应的是AOE-网(Activity On Edge)即边表示活动的网。AOE-网是一个带权的有向无环图，其中，顶点表示事件(Event)，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。
例如，图7.29是一个假想的有11项活动的AOE-网。其中有9个事件v1,v2,v3,…,v9，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如v1表示整个工程开始，v9表示整个工程结束，v5表示a4和a5已经完成，a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如，活动a1需要6天，a2需要4天等。
由于整个工程只有一个开始点和一个完成点，故在正常的情况（无环）下，网中只有一个入度为零的点（称作源点）和一个出度为零的点（叫做汇点）。
和AOV-网不同，对AOE-网有待研究的问题是：1） 完成整项工程至少需多长时间？ 2） 哪些活动是影响工程进度的关键？
由于在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度（这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目）。路径长度最长的路径叫做关键路径(Critical Path)。假设开始点是v1，从v1到vi的最长路径长度叫做事件vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间。还可以定义一个活动的的最迟开始时间l(i)，这是在不推迟整个工程完成的前提下，活动ai最迟必须开始的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。我们把l(i)=e(i)的活动叫做关键活动。显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。例如，图7.29中的网，从v1到v9的最长路径是(v1,v2,v5,v8,v9)，路径长度是18，即v9的最早发生时间是18。而活动a6的最早开始时间是5，最迟开始时间是8，这意味着：如果a6推迟3天或者延迟3天完成，都不会影响整个工程的完成。因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的工效，缩短整个工期。
由以上分析可知，辨别关键活动就是要找e(i)=l(i)的活动。为了求得AOE-网中活动的e(i)和l(i)，首先应求得事件的最早发生时间ve(j)和最迟发生时间vl(j)。如果活动ai由弧<j,k>表示，其持续时间记为dut(<j,k>)，则有如下关系：
这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提下进行。也就是说，ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定，而vl(j-1)则必须在vj的所有后继的最迟发生时间求得之后才能确定。因此，可以在拓扑排序的基础上计算ve(j-1)和vl(j-1)。
由此得到如下所述求关键路径的算法：
1） 输入e条弧<j,k>，建立AOE-网的存储结构；
2） 从原点v0出发，零ve[0]=0，按拓扑有序求其余顶点的最早发生时间ve[i](1<=i<=n-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，说明网中存在环，不能求关键路径，算法终止；否则执行步骤3）。
3） 从汇点vn出发，零vl[n-1]=ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i](n-2>=i>=2)；
4) 根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)，若某条弧满足条件e(s)=l(s)，则为关键活动。
如上所述，计算各顶点的ve值是在拓扑排序的过程中进行的，需对拓扑排序的算法作如下修改：
（a） 在拓扑排序之前设初值，令ve[i]=0(0<=i<=n-1)；
（b） 在算法中增加一个计算vj的直接后继vk的最早发生时间的操作： 若ve[j]+dut(<j,k>) > ve[k]，则ve[k]=ve[j] + dut(<j,k>)；
（c） 为了能按逆拓扑有序序列的顺序计算各顶点的vl值，需记下在拓扑排序的过程中求得的拓扑有序序列，这需要在拓扑排序算法中，增设一个栈以记录拓扑有序序列，则在计算求得各顶点的ve值之后，从栈顶至栈底便为逆拓扑有序序列。
下面先将算法7.12改成算法7.13，则算法7.14便为求关键路径的算法：
算法7.13
Status TopologicalOrder(ALGraph G, Stack &T)
{
//有向网G采用邻接表存储结构，求各顶点事件的最早发生时间ve(全局变量)
//T为拓扑序列顶点栈； S为零入度顶点栈
//若G无回路，则用栈T返回G的一个拓扑序列，且函数值为OK，否则为ERROR
FindInDegree(G, indegree); //对各顶点求入度indegree[0..vernum-1]
InitStack(S); //建零入度顶点栈S
for(i = 0; i<G.vexnum; i++){
if(!indegree[i])
Push(S, i); //入度为0者进栈
}
count = 0; //对输出顶点的个数进行计数
ve[0..G.vexnum-1] = 0; //初始化
while(!StackEmpty(S)){
Pop(S, j); Push(T, j); ++count; //j号顶点入T栈并计数
for(p = G.vertices[j].firstarc; p; p = p->nextarc){
k = p->adjvex; //对j号顶点的每个邻接点的入度减1
if(--indegree[k] == 0)
Push(S,k)
if(ve[j] + *(p->info) > ve[k])
vek[k] = ve[j] + *(p->info);
}
}
if(count < G.vexnum)
return ERROR; //该有向网有回路
else
return OK;
}算法7.14
Status CriticalPath(ALGraph G)
{
//G为有向网，输出G的各项关键活动
if(!TopologicalOrder(G, T))
return ERROR;
vl[0..G.vexnum-1] = ve[G.vexnum-1]; //初始化顶点事件的最迟发生时间
while(!StackEmpty(T)){ //按拓扑逆序求各顶点的vl值
for(Pop(T, j), p = G.vertices[j].firstarc; p; p = p->nextarc){
k = p->adjvex; dut = *(p->info); //dut<j,k>
if(vl[k] - dut < vl[j])
vl[j] = vl[k] - dut;
}
}
//求ee，el和关键活动
for(j = 0; j < G.vexnum; j++){
for(p = G.vertices[j].firstarc; p; p = p->nextarc){
k = p->adjvex; dut = *(p->info);
ee = ve[j];
el = vl[k] - dut;
tag = (ee == el) ? '*' : '';
printf(j, k, dut, ee, el, tag); //输出关键活动
}
}
}由于逆拓扑排序必定在网中无环的前提下进行，则可利用DFS函数，在退出DFS函数之前按式(7-3)计算顶点v的vl值（因为此时v的所有直接后继的vl值都已求出）。
这两种算法的时间复杂度均为O(n+e)，显然，前一种算法的常数因子要小些。由于计算弧的活动最早开始时间和最迟开始时间的复杂度为O(e)，所以总的求关键路径的时间复杂度为O(n+e)。
例如，对图7.30(a)所示网的计算结果如图7.31所示，可见a2、a5和a7为关键活动，组成一条从源点到汇点的关键路径。如图7.30(b)所示。
对于图7.29所示的网，可计算求得关键活动为a1，a4，a7，a8，a10和a11。如下图(图7.32)所示，它们构成两条关键路径：(v1,v2,v5,v7,v9)和(v1,v2,v5,v8,v9)。
实践已经证明：用AOE-网来估算某些工程的完成时间是非常有用的。实际上，求关键路径的方法本身最初就是与维修和建造工程一起发展的。但是，由于网中各项活动是互相牵涉的，因此，影响关键活动的因素亦是多方面的，任何一项活动持续时间的改变都会影响关键路径的改变。例如，对于图7.30(a)所示的网来说，若a5的持续时间改为3，则可发现关键活动数量增加，关键路径也增加。若同时将a4时间改成4，则(v1,v3,v4,v6)不再是关键路径。由此可见，关键活动的速度提高是有限度的，只有在不改变网的关键路径的情况下，提高关键活动的速度才有效。
另一方面，若网中有几条关键路径，那么单是提高一条关键路径上的关键活动的速度，还不能导致整个工程缩短工期，而必须提高同时在几条关键路径上的活动的速度。
[参看]:
