有向无环图及其应用

有向无环图•无环的有向图称为有向无环图，简称DAG图•P179图7.21：有向树、DAG图、有向图•DAG图可用于：描述含有公共子式的表达式；描述工程的进行过程；•有向无环图是描述一项工程进行过程的有效工具，主要进行拓扑排序和关键路径的操作。工程能否顺利进行—拓扑排序完成整个工程所需的最短时间—关键路径活动网络(ActivityNetwork)计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都可以将工程分为若干个称作“活动”的子工程，完成了这些活动，整个工程就可以完成了。例：计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一个活动，其中有些课程要求先修课程，有些则不要求，这样在有的课程之间就存在领先关系，而有的课程则可以并行学习。用顶点表示活动的网(AOV-网)C1高等数学C2程序设计基础C3离散数学C1,C2C4数据结构C3,C2C5高级语言程序设计C2C6编译原理C5,C4C7操作系统C4,C9C8大学物理C1C9计算机原理C8学生课程学习工程图C8C3C5C4C9C6C7C1C2可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边Vi,Vj表示活动Vi必须先于活动Vj进行。这种有向图称作顶点表示活动的AOV网(ActivityOnVertex)。在AOV网络中不能出现有向回路,即有向环。如果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的AOV网络，必须先判断它是否存在有向环。检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中,则该网络中必定不会出现有向环。如果AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。例如,对学生课程学习工程图进行拓扑排序,得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7或C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C2拓扑排序的方法①输入AOV网络，令n为顶点个数。②在AOV网络中选一个没有直接前驱的顶点,并输出之;③从图中删去该顶点,同时删去所有它发出的有向边;④重复以上②、③步,直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点,但已跳出处理循环。说明图中还剩下一些顶点,它们都有直接前驱。这时网络中必存在有向环。C0C1C2C3C4C5拓扑排序的过程(a)有向无环图C2C5C1C0C3(b)输出顶点C4C1C2C5C3(c)输出顶点C0C4C0C2C5C1C3(d)输出顶点C3C1C2C5(e)输出顶点C2C5C1(f)输出顶点C1C5(g)输出顶点C5最后得到的拓扑有序序列为C4,C0,C3,C2,C1,C5。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。(h)拓扑排序完成AOV网络及其邻接表表示C0C1C2C3C4C5C0C1C2C30C4C50012345indegreedataadj1301031destlink3051500150在邻接表中增设一个数组indegree[]，记录各顶点入度。入度为零的顶点即无前驱顶点。在算法中,使用一个存放入度为零的顶点的栈,供选择和输出无前驱的顶点。拓扑排序算法可描述如下：建立入度为零的顶点栈;当入度为零的顶点栈不空时,重复执行从顶点栈中退出一个顶点,并输出之;从AOV网络中删去这个顶点和它发出的边,边的终顶点入度减一;如果边的终顶点入度减至0,则该顶点进入度为零的顶点栈;如果输出顶点个数少于AOV网络的顶点个数,则报告网络中存在有向环。P182算法7.12用边表示活动的网络(AOE网)如果在带权的有向无环图中,用有向边表示一个工程中的活动(Activity),用边上权值表示活动持续时间(Duration),用顶点表示事件(Event),则这样的有向图叫做用边表示活动的网络,简称AOE(ActivityOnEdges)网。AOE网在某些工程进度估算方面非常有用。例如，可以使人们了解：完成整个工程至少需要多少时间(假设网络中没有环)?为缩短完成工程所需的时间,应当加快哪些活动?从源点到各个顶点,以及从源点到汇点的有向路径可能不止一条，这些路径的长度也可能不同，完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了,整个工程才能完成。因此,完成整个工程所需的时间取决于从源点到汇点的最长路径长度,即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径叫做关键路径(CriticalPath)。a9=61324a1=8a2=125678a10=12a8=18a5=28a6=8a7=6a3=14a4=10要找出关键路径，必须找出关键活动,即不按期完成就会影响整个工程完成的活动。关键路径上的所有活动都是关键活动。因此,只要找到了关键活动,就可以找到关键路径。例如,下图就是一个AOE网。定义几个与计算关键活动有关的量：①事件Vi的最早发生时间ve(i)是从源点V0到顶点Vi的最长路径长度②事件Vi的最迟发生时间vl[i]是在保证汇点Vn-1在ve[n-1]时刻完成（即不影响整个工程工期）的前提下，事件Vi允许的最迟开始时间。③活动ak的最早可能开始时间e[k]设活动ak在弧Vi,Vj上,则e[k]是从源点V0到顶点Vi的最长路径长度。因此,e[k]=ve[i]④活动ak的最迟允许开始时间l[k]在不会引起整个工程时间延误的前提下,该活动允许的最迟开始时间。l[k]=vl[j]-dur(i,j)。其中,dur(i,j)是完成ak所需的时间。⑤时间余量l[k]-e[k]表示活动ak的最早可能开始时间和最迟允许开始时间的时间余量。l[k]==e[k]表示活动ak是没有时间余量的关键活动。为找出关键活动,需要求出各个活动的e[k]与l[k]，以判别是否l[k]==e[k]。为求得e[k]与l[k],需要先求得从源点V0到各个顶点Vi的ve[i]和vl[i]。求ve[i]和vl[i]的递推公式从ve[0]=0开始，向前递推Vj,ViS2,i=1,2,,n-1S2是所有指向Vi的有向边Vj,Vi的集合。从vl[n-1]=ve[n-1]开始，反向递推Vi,VjS1,i=n-2,n-3,,0S1是所有源自Vi的有向边Vi,Vj的集合。},),(][{][ijjVVdurjVemaxiVe},),(][{][jijVVdurjVlminiVl这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。设活动ak(k=1,2,…,e)在带权有向边Vi,Vj上,其持续时间用dur(Vi,Vj)表示,则有e[k]=ve[i]；l[k]=vl[j]-dur(Vi,Vj)；k=1,2,…,e。这样就得到计算关键路径的算法。为了简化算法,假定在求关键路径之前已经对各顶点实现了拓扑排序,并按拓扑有序的顺序对各顶点重新进行了编号。对算法7.12作如下修改得算法7.13：（算法7.13求各事件的ve）①设初值ve(i)=0(0≤i≤n-1)②计算Vj的直接后继Vk的ve(k)：若ve(j)+dut(j,k)ve(k)则ve(k)=ve(j)+dut(j,k)③为求vl，设一栈记录拓扑有序序列，之后弹栈求逆拓扑有序序列算法7.14（先求各事件的vl，再求各活动的e和l（7.14中用ee和el表示），当某个活动的e=l，则该活动是关键活动）1324a1=8a2=125678a10=12a9=6a8=18a5=28a6=8a7=6a3=14a4=10VeVl123456780812222840465808122228404658el008121222222840460081212322228404612345678910三条关键路径：1-2-4-5-7-81-3-4-5-7-81-3-6-7-8注意所有顶点按拓扑有序的次序编号仅计算ve[i]和vl[i]是不够的，还须计算e[k]和l[k]。不是任一关键活动加速一定能使整个工程提前。想使整个工程提前，要考虑各条关键路径上所有关键活动。