拓扑排序和关键路径

7.5有向无环图及其应用•有向无环图：一个无环的有向图，简称DAG图。•有向无环图的实际应用有向无环图是描述工程或系统进行过程的有效工具。对整个工程和系统，人们最关心的是两个方面的问题：（1）工程能否顺利进行；（2）工程完成所必需的最短时间。归结到有向图中，就是进行拓扑排序和求解关键路径的问题。•AOV-网用顶点表示活动，用边来表示活动之间的先后关系的有向图称为顶点活动网，简称AOV-网。例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。7.5.1拓扑排序C1高等数学C2程序设计基础C3离散数学C1,C2C4数据结构C3,C2C5高级语言程序设计C2C6编译方法C5,C4C7操作系统C4,C9C8普通物理C1C9计算机原理C8课程代号课程名称先修课程学生课程学习工程图C8C3C5C4C9C6C7C1C2在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网络中选一个没有直接前驱的顶点,并输出之;③从图中删去该顶点,同时删去所有它发出的有向边;④重复以上②、③步,直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点,但已跳出处理循环。说明图中还剩下一些顶点,它们都有直接前驱。这时网络中必存在有向环。C0C1C4C3C2C5拓扑排序的过程(a)有向无环图C4C5C1C0C3(b)输出顶点C2C1C4C5C3(c)输出顶点C0C2C0C4C5C1C3(d)输出顶点C3C1C4C5(e)输出顶点C4C5C1(f)输出顶点C1C5(g)输出顶点C5最后得到的拓扑有序序列为C2,C0,C3,C4,C1,C5。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C2和C4，也排出了先后次序关系。(h)拓扑排序完成AOV网络及其邻接表表示C0C1C4C3C2C5C0C1C2C30C4C50012345indegreedatafirstarc1301031adjvexnextarc30501500150在邻接表中增设一个数组indegree[]，记录各顶点入度。在拓扑排序前前,初始化入度数组。入度为零的顶点即无前驱顶点。在算法中,使用栈存放入度为零的顶点,供选择和输出无前驱的顶点。拓扑排序算法可描述如下：入度为零的顶点入栈;当栈不空时,重复执行从顶点栈中退出一个顶点,并输出之;从AOV网络中删去这个顶点和它发出的边,边的终顶点入度减一;如果边的终顶点入度减至0,则该顶点进栈;如果输出顶点个数少于AOV网络的顶点个数,则报告网络中存在有向环。拓扑排序的算法voidTopologicalSort(ALGraphG){FindInDegree(G,indegree);//初始化indegree[]InitStack(S);for(i=0;iG.vexnum;i++)//入度为零的顶点if(indegree[i]==0)Push(S,i);//进栈count=0;//对输出顶点计数while(!StackEmpty(S)){Pop(S,i);//退栈coutiG.vertices[i].data;//输出i号顶点count++;//并计数//扫描i号顶点的每个邻接点for(p=G.vertices[i].firstarc;p;p=p-nextarc){k=p-adjvex;if(--indegree[k]==0)//顶点入度减1Push(S,k);//顶点的入度减至零,进栈}}}7.5.2关键路径一、AOE网如果在有向无环图中,用有向边表示一个工程中的活动(Activity),用边上权值表示活动持续时间(Duration),用顶点表示事件,则这样的有向图叫做用边表示活动的网络,简称AOE(ActivityOnEdges)网。AOE网络在某些工程估算方面非常有用。例如，可以使人们了解：完成整个工程至少需要多少时间(假设网络中没有环)?为缩短完成工程所需的时间,应当加快哪些活动?从源点到汇点的路径可能不止一条，并且这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同,但只有各条路径上所有活动都完成了,整个工程才算完成。因此,完成整个工程所需的时间取决于从源点到汇点的最长路径长度,即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(CriticalPath)。要找出关键路径，必须找出关键活动,即不按期完成就会影响整个工程完成的活动。关键路径上的所有活动都是关键活动。因此,只要找到了关键活动,就可以找到关键路径。例如,下图就是一个AOE网。V1V3V2V4V5V6a7=2a4=3a8=1二、相关术语①事件Vi的最早发生时间ve(i)是从源点V0到顶点Vi的最长路径长度。②事件Vi的最迟发生时间vl(i)在不推迟整个工程完成的前提下，事件Vi的最迟发生时间。③活动ai的最早开始时间e(i)④活动ai的最迟开始时间l(i)表示在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的事件。⑤时间余量l(i)–e(i)表示活动ai的最早可能开始时间和最迟允许开始时间的时间余量。l(i)=e(i)的活动称为关键活动。三、怎样求关键路径？如何找e(i)=l(i)的关键活动？为找出关键活动,需要求各个活动的e(i)与l(i)，以判别是否l(i)=e(i)。设活动ai由弧Vj,Vk表示，且活动持续时间记为dut(j,k),则e(i)=ve(j)l(i)=vl(k)-dut(j,k)VjVkai如何求ve(i)和vl(i)？求ve(i)的递推公式从ve(0)=0开始，向前递推i,jT,i=1,2,,n-1T是所有以第j个顶点为头的弧的集合。例，求右图中顶点V6的最早发生时间。}),({)(jivjvedute(i)maxiV3V4V5V6a7=2a8=1266V1V2V3V4V5V6顶点vevl032668V1V3V2V4V5V6a7=2a4=3a8=1032668求vl(i)的递推公式从vl(n-1)=ve(n-1)开始，反向递推i,jS,i=n-2,n-3,,0S是所有以第i个顶点为尾的弧的集合。例，求右图中顶点V1的最迟发生时间。}),()(v{)(jidutjlMinivljV1V3V224V1V2V3V4V5V6顶点vevl032668V1V3V2V4V5V6a7=2a4=3a8=1042678042678a1a2a3a4a5a6a7a8活动ell-e011000341220253660671341V1V3V2V4V5V6a7=2a4=3a8=1V1V2V3V4V5V6顶点vevl032668042678四、算法实现实现步骤：①输入e条弧j,k，建立AOE-网的存储结构；②从源点v0出发，令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间ve[i]（1≤i≤n-1）。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤③。③从汇点vn出发，令vl[n-1]=ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i]（n-2≥i≥2）；④根据各顶点的ve和vl的值，求每条弧s的最早发生时间e(s)和最迟发生时间l(s)。若某条弧满足条件e(s)=l(s)，则为关键活动。算法实现StatusTopologicalOrder(ALGraphG,Stack&T){//求各顶点事件的最早发生时间ve（全局变量），T为拓扑序列顶点栈FindInDegree(G,indegree)；//对各顶点求入度InitStack(T)；count=0；ve[0..G.vexnum-1]=0；//初始化while(!StackEmpty(S))//S为零入度顶点栈{Pop(S,j)；push(T,j)；++count；//j号顶点入T栈并计数for(p=G.vertices[j].firstarc；p；p=p→nextarc){k=p→adjvex；//对j号顶点的每个邻接点的入度减1if(--indegree[k]==0)push(S,k)；if(ve[j]+*(p→info)ve[k])ve[k]=ve[j]+*(p→info)；}}if(countG.vexnum)returnERROR；//该有向网有回路elsereturnOK；}StatusCriticalPath(ALGraphG){//G为有向网，输出G的各项关键活动if(!TopologicalOrder(G,T)returnERROR;vl[0..G.vexnum-1]=ve[0..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)；if(vl[k]-dutvl[j])vl[j]=vl[k]-dut；}for(j=0；jG.vexnum；++j)//求ee，el和关键活动for(p=G.vertices[j]；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)；//输出关键活动}}算法时间复杂度分析在拓扑排序求ve[i]和逆拓扑有序求vl[i]时，算法的时间复杂度为O(n+e)，求各个活动的e[k]和l[k]时复杂度为O(e)，所以总的求关键路径的时间复杂度为O(n+e)。五、注意用AOE-网来估算某些工程完成的时间是非常有用的。影响关键活动能够的因素也是多方面的，任何一项活动持续时间的改变都会影响关键路径的改变。思考题：图7.30中a5的持续时间改为3，关键活动和关键路径如何变化？若同时将a4的时间改为4，关键活动和关键路径如何变化？提高关键活动的工效，可缩短整个工期。关键活动的速度提高是有限度的。只有在不改变网的关键路径的情况下，提高关键活动的速度才有效。关键路径有时也不是唯一的，因此要缩短工期，必须提高所有关键路径上的活动的工效。