有向无环图及其应用.ppt

有向无环图活动网络(ActivityNetwork)C1高等数学
C2程序设计基础
C3离散数学C1,C2
C4数据结构C3,C2
C5高级语言程序设计C2
C6编译原理C5,C4
C7操作系统C4,C9
C8大学物理C1
C9计算机原理C8学生课程学习工程图可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边<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,C6拓扑排序的方法在邻接表中增设一个数组indegree[]，记录各顶点入度。入度为零的顶点即无前驱顶点。
在算法中,使用一个存放入度为零的顶点的栈,供选择和输出无前驱的顶点。
拓扑排序算法可描述如下：
建立入度为零的顶点栈;
当入度为零的顶点栈不空时,重复执行
从顶点栈中退出一个顶点,并输出之;
从AOV网络中删去这个顶点和它发出的边,边的终顶点入度减一;
如果边的终顶点入度减至0,则该顶点进入度为零的顶点栈;
如果输出顶点个数少于AOV网络的顶点个数,则报告网络中存在有向环。
P182算法7.12用边表示活动的网络(AOE网)为缩短完成工程所需的时间,应当加快哪些活动?
从源点到各个顶点,以及从源点到汇点的有向路径可能不止一条，这些路径的长度也可能不同，完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了,整个工程才能完成。
因此,完成整个工程所需的时间取决于从源点到汇点的最长路径长度,即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径叫做关键路径(CriticalPath)。a9=6定义几个与计算关键活动有关的量：④活动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-1
S2是所有指向Vi的有向边<Vj,Vi>的集合。
从vl[n-1]=ve[n-1]开始，反向递推

<Vi,Vj>S1,i=n-2,n-3,,0
S1是所有源自Vi的有向边<Vi,Vj>的集合。
这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。
设活动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，则该活动是关键活动）1注意