拓扑排序(精)

*,*,单击此处编辑母版标题样式,第八章 排序,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第七章 图,7.6,拓扑排序,拓扑排序的基本概念,拓扑排序的基本要求,拓扑排序的算法实现,AOE,网络及其应用,2024/10/28,1,第八章 排序,第七章 图,拓扑排序的基本概念,图的应用,产生满足时间制约有关的排序结果,2024/10/28,2,第八章 排序,第七章 图,与拓扑排序有关的基本概念,研究对象,：有向无环图,逻辑含义,：定点表示某种活动，有向边表示活动之间次序上的制约关系,工作目标,：构造图中顶点满足次序制约关系的线性序列，这个序列称为拓扑序列，,2024/10/28,3,第八章 排序,第七章 图,与拓扑排序有关的应用,实例1：,工程设计（设计、勘测、外部施工、内部施工（内部的次序）,实例2：,课程设置，包含先休课程之间的制约关系,实例,3,：房屋装修,，墙壁，门框，地板，门,2024/10/28,4,第八章 排序,第七章 图,拓扑排序要求与特点,：,对于,有向无环图,结点的一种排序,若结点,V,与结点,U,之间存在,V,到,U,的边，则在拓扑序列中结点,V,一定排列在结点,U,之前。,最终的结果是一个满足时间制约关系结点序列,存在环路的有向图不存在拓扑序列。因为环路导致序列不可能满足上述原则。,一个有向无环图的拓扑序列不唯一。,2024/10/28,5,第八章 排序,AOV,图,与拓扑排序有关的概念,AOV,图：有向无环图的一种名称，由于这种图往往只由活动于它们次序间的制约关系构成，所以图又称为“活动网络”，英文表示为：,Activity On Vertex,AOV,（活动顶点）。通常，拓扑排序就是针对,AOV,图来考虑的。,AOV,图的拓扑序列，就是满足图中结点之间次序制约关系的结点序列。,2024/10/28,6,第八章 排序,拓扑排序的控制思想,有向无环图，至少存在一个以上入度为,0,的结点，该类结点就是拓扑序列的起始结点，在工程上就表示工程中第一步可做的工作。,处理一个结点的操作就是删除该结点的所有出边。这一操作的结果可以导致，当某一结点的直接前驱结点都处理完成，则该结点的入度就为,0,了。在课程设置上表示，当某课程的所有先修课都学过了，这门课程就可以选修（激活）了。,基于上述思想我们讨论拓扑排序的程序设计。,2024/10/28,7,第八章 排序,第七章 图,拓扑排序的实现,我们将考虑几种实现拓扑排序过程，对于含有回路的有向图，算法将说明，图中含有回路，不存在拓扑排序。,2024/10/28,8,第八章 排序,拓扑排序算法说明-1,存储结构：,邻接矩阵,与,辅助结构,，结点数为,N,计算所有未处理结点的入度,（不存在未处理结点结束）,选取,入度为 0,的结点,V,满足要求的,V,存在吗？存在,goto,5,，否则,goto,7,输出,V；,删除,V,所有,出边,；标记,V,的处理结束,修正处理结点计数器,total+;,goto,2;,提示“,ring”,（若,total,data.count,-;/,相应结点入度,-1,wp,=,wp,-next;,hk.count,=-1;/,标志结点处理结束,当所有结点的,count,为,-1,时，处理结束,2024/10/28,29,第八章 排序,拓扑排序实例,0,1,4,2,5,3,0,4,1,2,5,3;0,4,1,5,2,3;0,4,5,1,2,3,4,0,1,2,5,3;4,0,1,5,2,3;4,0,5,1,2,3,4,5,0,1,2,3;,2024/10/28,30,第八章 排序,拓扑排序的要求,了解拓扑排序的算法思想,对指定的数据序列能写出其所有的拓扑序列,2024/10/28,31,第八章 排序,AOE,网络与关键路径,所有的工程或系统都可以分为若干个称作活动（,activity,）的子工程，而这些子工程之间，通常存在着一定的制约关系，如其中的某些子工程必须在另外一些子工程完成之后开始。对于整个工程或系统，我们关心的是两个方面的问题：,工程能否顺利完成？（,AOV,网络）,工程完成所必需的最短时间？（,AOE,网络）,2024/10/28,32,第八章 排序,AOV,网,AOV,（,Activity On Vertex Network,）：,用顶点表示活动，用边表示活动间的优先,(,制约,),关系的有向图,，称为顶点表示活动的网络，简称为,AOV,网。,2024/10/28,33,第八章 排序,AOV,网,利用,AOV,网络，我们试图解决各个活动之间的关系问题，典型的实例：,教学计划制定中课程及课程间的先修关系可用,AOV,网表示任何无环路的,AOV,网，其顶点都可以排成一个拓扑序列，并且其拓扑序列不一定是唯一的。,2024/10/28,34,第八章 排序,1,2,3,4,5,6,7,8,9,10,2024/10/28,35,第八章 排序,AOE,网,AOE,网（,Activity On Edge Network,）在带权的有向图中，用结点表示事件，用边表示活动，边上权表示活动的开销（如持续时间），则称此有向图为边表示活动的网络,简称,AOE,网。,下图是有,11,项 活动，,9,个事件的,AOE,网，每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。,2024/10/28,36,第八章 排序,AOE,网络,因为活动可以并行，从源点到汇点存在多条路径,带权路径长度最长的路径成为,“关键路径”,关键路径中活动称为,“关键活动”,2024/10/28,37,第八章 排序,AOE,网,AOE,网的性质：,只有在某个顶点所代表的事件发生后，从该顶点出发的各有向边代表的活动才能开始,;,只有在进入某一顶点的各有向边代表的活动已经结束，该顶点所代表的事件才能发生；,表示实际工程计划的,AOE,网应该是无环的，并且存在唯一的入度为,0,的开始顶点（源点）和唯一的出度为,0,的结束点（汇点）。,2024/10/28,38,第八章 排序,AOE,网,AOE,网研究的主要问题：,如果用,AOE,网表示一项工程，那么仅仅考虑各个子工程之间的优先关系还不够，更多地是关心整个工程完成的最短时间是多少，哪些活动的延迟将影响整个工程进度,而加速这些活动能否提高整个工程的效率,因此,AOE,网有待研究的问题是,:,完成整个工程至少需要多少时间？,哪些活动是影响工程进度的关键活动？由于工程中某些活动是可以并行的，所以并不是缩短任一活动的时间都能够达到缩短整个工程工期的目的。,2024/10/28,39,第八章 排序,关键路径与关键活动性质分析,考察关键路径描述的特征点（参数）：,事件,Vj,的可能发生的最早时间,VE(j,),：,是从源点,V1,到顶点,Vj,的最长路径长度。,活动,ai,可能开始的最早时刻,E(k,),：,设活动,ai,在边,上,则,E(i,),也就是从源点,V1,到顶点,Vj,的最长路径长度。这是因为事件,Vj,发生表明以,Vj,为起点的所有活动,ai,可以立即开始。,因此有：,E(i,)=,VE(j,).(1),即：活动最少开始时间就是相应起始结点事件开始的最早时间。,2024/10/28,40,第八章 排序,关键路径与关键活动,事件,Vk,的最迟发生时间,VL(k,),：,是指在保证汇点,Vn,在,VE(n,),时刻完成的前提下，事件,Vk,允许的最迟开始时间。就是说：在不推迟工期的情况下，事件,Vk,最迟发生时间,VL(k,),应该等于汇点的最早发生时间,VE(n,),减去从,Vk,到,Vn,的最大路径长度。,2024/10/28,41,第八章 排序,关键路径与关键活动,活动,ai,允许的最迟开始时间,L(i,),：,是指在不会引起工期延误的前提下，活动,ai,允许的最迟开始时间。因为事件,Vk,发生表明以,Vk,为终点的入边所表示的所有活动均已完成，所以事件,Vk,的最迟发生时间,VL(k,),也是所有以,Vk,为终点的入边：,所表示的活动,ai,可能的最迟完成时间。,所以，若要保证不推迟工期，活动,ai,的最迟开始时间,L(i,),应该是,ai,的最迟完成时间,VL(k,),减去,ai,的持续时间，即：,L(i,)=,VL(k,)-,ACTjk,.(2),其中,ACTjk,是活动,ai,的持续时间，即边（,上的权）。,2024/10/28,42,第八章 排序,关键路径与关键活动,时间余量,D,（,i,）：,D(i,)=,L(i,)-,E(i,),，,L(i,)-,E(i,),表示活动,ak,的最早可能开始时间和最迟允许开始时间的差，即活动允许的拖延时间,-,时间余量。,工程从源点到汇点的路径中，时间最高的路径为关键路径。,关键路径上的活动都满足：,L(i,)=,E(i,).(3),L(i,)=,E(i,),表示没有时间余量的活动，即关键活动。,综上所述，为找出关键活动，需要求各个活动的,E(i,),与,L(i,),，以判别一个活动,ai,是否 满足,L(i,)=,E(i,),。,E(i,),和,L(i,),可有公式,(1),和,(2),。而,VE(k,),和,VL(k,),可由拓扑分类算法的到。,2024/10/28,43,第八章 排序,事件与活动,事件,2,事件,3,事件,1,活动,1,活动,2,活动,3,事件最早开始时刻,VE,=,活动最早开始时刻,E,事件,3,的,最早开始时刻,VE,=,前件,活动的最迟完成时刻,VL,2024/10/28,44,第八章 排序,事件与活动,事件,2,事件,3,事件,1,活动,1,活动,2,活动,3,时间余量,D,在保证活动期限不拖延的前提下，,活动最迟开始时刻,活动,1,的最早开始与最迟开始时刻是相同的，活动,1,为关键活动，只有活动,1,的改进和提前能够影响整个工程的工期,2024/10/28,45,第八章 排序,关键路径与关键点计算,（拓扑分类算法）,Step1(,前进阶段,),：,计算事件,j,最早发生时间,Ve(j),：事件,Vj,可能发生的最早时刻，即,V1,到,Vj,的最长带权路径长度,0 j=1,Ve(j)=max(Ve(i)+(ViVj)j=2,3,n,ViVj,是边,ACT i j,2024/10/28,46,第八章 排序,关键路径与关键点计算,（拓扑分类算法）,Step2(,回退阶段,),：,计算事件,i,最晚发生时间,Vl(i),：保证不延误工期的前提下，允许事件,Vi,发生的最晚时刻,Ve(n)i=n,Vl(i)=min(Vl(j)-(ViVj)i=n-1,2,1,ViVj,是边,ACT i j,2024/10/28,47,第八章 排序,关键路径与关键点计算,（拓扑分类算法）,Step3,：求每一项活动（边）,ai,的,最早开始时间,:E(i)=VE(j),最晚开始时间,:L(i)=VL(k)-ACT j k,若某条边满足,E(i)=L(i),，则它是关键活动。,为了简化算法,可以在求关键路径之前已经对各顶点实现拓扑排序,并按拓扑有序的顺序对各顶点重新进行了编号。不是任意一个活动的加速一定能使整个工程提前。想使整个工程提前结束，需要要考虑各个关键路径上所有关键活动。,2024/10/28,48,第八章 排序,图程序设计综述,问题分析,遍历、最小生成树、最短路经、拓扑排序,算法选择,基于队列？堆栈？，,Prim,，,Kruskal,，,Dijkstra,存储设计,邻接矩阵、邻接表、边集数组,程序设计,2024/10/28,49,第八章 排序,