《数据结构拓扑排序课件》由会员分享，可在线阅读，更多相关《数据结构拓扑排序课件（29页珍藏版）》请在金锄头文库上搜索。
1、数数 据据 结结 构构 DATA STRUCTURE, DS 拓扑排序拓扑排序数据结构课程内容数据结构课程内容图结构的应用图结构的应用3 拓扑排序拓扑排序图结构的应用图结构的应用4 关键路径关键路径8.7 拓扑排序拓扑排序（topological sort）n先决条件问题先决条件问题n拓扑排序拓扑排序n将一个有向将一个有向无环图中所无环图中所有顶点在不有顶点在不违反违反先决条先决条件关系件关系的前的前提下排成线提下排成线性序列的过性序列的过程称为程称为拓扑拓扑排序排序学生选修课程问题：学生选修课程问题：学生学生应按怎样的顺序应按怎样的顺序学习学习下列下列课程，才能课程，才能无矛盾、顺利地完成无
2、矛盾、顺利地完成学业学业？课程代号课程名称 先修课先修课C1程序设计基础无C2离散数学C1C3数据结构C1,C2C4汇编语言C1C5语言的设计和分析C3,C4C6计算机原理C11C7编译原理C3.C5C8操作系统C3,C6C9高等数学无 C10线性代数C9C11普通物理C9C12数值分析C1,C9,C10C1C2C3C4C5C6C7C8C9C10C11C12数学模型：有向无环图数学模型：有向无环图顶点顶点活动（课程）活动（课程）有向弧有向弧活动活动i是活动是活动j的先决条件的先决条件序列序列1：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8序列序列2：C9-C10
3、-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8Activity OnVertex network8.7 拓扑排序（续）拓扑排序（续）n拓扑序列拓扑序列(Topological order)n对于对于有向无环图有向无环图G=(V, E), 所有顶点组成的所有顶点组成的线性序列如果满足线性序列如果满足n若在有向无环图若在有向无环图G中从顶点中从顶点Vi到到Vj有一条路径，有一条路径，则在序列中顶点则在序列中顶点Vi必在顶点必在顶点Vj之前之前则该线性序列可称作一个则该线性序列可称作一个拓扑序列拓扑序列。n拓扑序列不唯一拓扑序列不唯一8.7 拓扑排序（续）拓扑排序（续）n任何有向无
4、环图任何有向无环图G的所有顶点都可以排的所有顶点都可以排在一个拓扑序列里。在一个拓扑序列里。n拓扑排序的方法是：拓扑排序的方法是：n1、从图、从图G中选择一个入度为中选择一个入度为0的顶点并输的顶点并输出。出。n2、从图、从图G中删掉此顶点及其所有的出边。中删掉此顶点及其所有的出边。n3、回到第、回到第1步继续执行，直至步继续执行，直至G所有顶点所有顶点都被输出或都被输出或G中不存在入度为中不存在入度为0的顶点的顶点。C1C2C3C4C5C6C7C8C9C10C11C12C2C3C4C5C6C7C8C9C10C11C12（1）拓扑序列：C1C3C4C5C6C7C8C9C10C11C12（2）拓
5、扑序列：C1-C2C4C5C6C7C8C9C10C11C12（3）拓扑序列：C1-C2-C3C5C6C7C8C9C10C11C12（4）拓扑序列：C1-C2-C3-C4C6C8C10C11C12（7）拓扑序列：C1-C2-C3-C4 -C5-C7-C9C6C8C11C12（8）拓扑序列：C1-C2-C3-C4 -C5-C7-C9-C10C6C7C8C9C10C11C12（5）拓扑序列：C1-C2-C3-C4 -C5C6C8C9C10C11C12（6）拓扑序列：C1-C2-C3-C4 -C5-C7C6C8C12（9）拓扑序列：C1-C2-C3-C4 -C5-C7-C9-C10-C11C8C12（
6、10）拓扑序列：C1-C2-C3-C4 -C5-C7-C9-C10-C11-C6C8（11）拓扑序列：C1-C2-C3-C4 -C5-C7-C9-C10-C11-C6 -C12（12）拓扑序列：C1-C2-C3-C4 -C5-C7-C9-C10-C11-C6 -C12-C8n拓扑排序算法首先需要计算拓扑排序算法首先需要计算各顶点的入度，然各顶点的入度，然后后在拓扑排序过程中，当某个顶点的入度为零在拓扑排序过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有直时，就将此顶点输出，同时将该顶点的所有直接后继顶点的入度减接后继顶点的入度减1。为了。为了避免重复避免重复检测入检测入度为零
7、的顶点，设立一个度为零的顶点，设立一个栈（或队列），栈（或队列），以保以保存当前所有存当前所有“入度为零入度为零”的顶点的顶点n若有向若有向G中所有顶点都被输出中所有顶点都被输出，则表明，则表明G中中没没有有向环有有向环，拓扑排序成功。若仅输出了部分顶，拓扑排序成功。若仅输出了部分顶点，点，G中已不存在入度为中已不存在入度为0的顶点，则表明的顶点，则表明G中中存在有向环，拓扑排序失败。存在有向环，拓扑排序失败。n拓扑排序算法实现：设图拓扑排序算法实现：设图G G的顶点数为的顶点数为n nn1 1、对各顶点求入度对各顶点求入度n2 2、初始化栈、初始化栈S Sn3 3、把所有入度为把所有入度为0
8、 0的顶点入栈的顶点入栈S Sn4 4、当栈、当栈S S非空时循环非空时循环n4.1 4.1 访问栈顶元素访问栈顶元素v v并出栈；并出栈；n4.2 4.2 获得所有与获得所有与v v邻接的未被访问的顶点邻接的未被访问的顶点w wn4.3 4.3 把把w w的入度减的入度减1 1；n4.4 4.4 若若w w的入度为的入度为0 0则入栈则入栈S S直至栈直至栈S S空为止空为止5 5、如果存在顶点未被访问，则有向图有环，不存在拓扑序列，、如果存在顶点未被访问，则有向图有环，不存在拓扑序列，拓扑排序失败；否则，拓扑排序成功拓扑排序失败；否则，拓扑排序成功6 6、结束、结束987645321123
9、456789 data adjhead12546 7 8840123456783dest next7栈栈(底底-顶顶)拓扑序列拓扑序列0v13,2,1v23,2v33,4v53,6v73v45v67v88v9空空例如：例如：8.7 拓扑排序（续）拓扑排序（续）n拓扑排序算法的时间复杂度分析拓扑排序算法的时间复杂度分析n关键是，算法在开始时要找出所有入度为关键是，算法在开始时要找出所有入度为0的顶点（同时可知道其它顶点的入度）的顶点（同时可知道其它顶点的入度）n当采用当采用邻接矩阵邻接矩阵时，算法在开始时找所有时，算法在开始时找所有入度为入度为0的顶点需要的顶点需要 O (n2)的时间，加上的时
10、间，加上处理边、顶点的时间，总代价为处理边、顶点的时间，总代价为O(n2+e+n)= O (n2)n当采用当采用邻接表邻接表时，因为在顶点表的每个顶时，因为在顶点表的每个顶点中可以有一个字段来点中可以有一个字段来存储入度存储入度，所以算，所以算法在开始时找所有入度为法在开始时找所有入度为0的顶点只需要的顶点只需要O(e)的时间，加上处理边、顶点的时间，的时间，加上处理边、顶点的时间，总代价为总代价为O(n+2e)=O(n+e)n工程计划有关问题工程计划有关问题把工程计划表示为有向无环图把工程计划表示为有向无环图G，用，用顶点表示事件顶点表示事件，弧表示活弧表示活动，权表示活动持续时间动，权表示
11、活动持续时间。每个事件表示在它之前的活动已每个事件表示在它之前的活动已完成，在它之后的活动可以开始（约束条件）完成，在它之后的活动可以开始（约束条件）例：设一个工程有例：设一个工程有m=11项活动，项活动，n=9个事件，其中事件个事件，其中事件vj 事件事件v1表示整个工程开始表示整个工程开始(记为记为v) 事件事件v9表示整个工程结束表示整个工程结束(记为记为vn) 活动活动ai用弧用弧表示，其持续时间记为表示，其持续时间记为dut()问题：问题：（1）完成整项工程）完成整项工程至少至少需要多少时间？需要多少时间？ （2）哪些活动是影响工程进度的）哪些活动是影响工程进度的关键活动关键活动？9
12、87645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=48.8 关键路径关键路径n定义定义1nAOE网网(Activity On Edge network, 边表示活动的边表示活动的网网)是一个是一个顶点表示事件，弧表示活动，权表示活动顶点表示事件，弧表示活动，权表示活动持续时间持续时间的带权有向无环图。网中仅存在一个入度的带权有向无环图。网中仅存在一个入度为为0的顶点，称作的顶点，称作开始顶点开始顶点；网中仅存在一个出度为；网中仅存在一个出度为0的顶点，称为的顶点，称为结束顶点结束顶点n距离距离路径上各活动持续时间之和路径上各活动持续时间之
13、和n关键路径关键路径从开始顶点到结束顶点的从开始顶点到结束顶点的距离最长距离最长的的路径路径 n由于由于AOE网中某些活动可以同时进行，网中某些活动可以同时进行，要保证每个活动要保证每个活动都能无矛盾顺利完成都能无矛盾顺利完成(约束条件约束条件)，完成该工程的最少时间完成该工程的最少时间就是该工程就是该工程AOE网的网的关键路径距离关键路径距离。987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4n定义定义2 2nVe(j)表示表示事件事件vj的最早的最早(early)发生时间，是从开发生时间，是从开始顶点始顶点v到到vj的的最长最长路
14、径距离。其中路径距离。其中Ve(n)是是该工程该工程AOE网的关键路径距离网的关键路径距离。?如何计算如何计算nVl(j)表示事件表示事件vj的最迟的最迟(last)发生时间，是在不发生时间，是在不推迟整个工程完成推迟整个工程完成(即即保证结束顶点保证结束顶点vn在在Ve(n)时刻发时刻发生生)的前提下的前提下,该事件最迟必须发生的时间该事件最迟必须发生的时间。nVl(j)=Ve(n) 顶点顶点vj到结束顶点到结束顶点vn的最长路径距离。的最长路径距离。？如何计算？如何计算987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4064577
15、161418987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4Ve示例示例0668710161418Vl示例示例n定义定义3 3ne(i)表示表示活动活动ai的最早的最早(early)开始时间，是该活开始时间，是该活动的动的起点起点所表示事件的所表示事件的最早最早发生时间发生时间n如果边如果边表示活动表示活动ai，则有，则有e(i)=Ve(j)nl(i)表示活动表示活动ai的最迟的最迟(last)开始时间，是该活开始时间，是该活动的动的终点终点所表示事件的所表示事件的最迟最迟发生时间与该活动的所发生时间与该活动的所需时间之差需时间之差
16、n如果边如果边表示活动表示活动ai，则有则有l(i)=Vl(k)-dut()987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=40645771614007e示例示例06687101614732l示例示例0645771614180668710161418vjvkain定义定义4 4nl(i)-e(i)表示完成活动表示完成活动ai的的时间余量时间余量，它是在不，它是在不增加完成整个工程所需时间的情况下，活动增加完成整个工程所需时间的
17、情况下，活动ai可以可以拖延的时间拖延的时间n关键活动关键活动关键路径上的活动，即关键路径上的活动，即l(i)=e(i)的活的活动动987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=40645771614007计算计算e06687101614732计算计算l987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4关键路径关键路径n如何找如何找e(i)=l(i)的关键活动？的关
18、键活动？设事件数为设事件数为n，活动数为，活动数为m。活动。活动ai用弧用弧表示，其持续时间记为表示，其持续时间记为dut()，则有：则有：（1）e(i)=Ve(j)（2）l(i)=Vl(k) -dut()vjvkain如何求如何求Ve(j)和和Vl(j)？继而如何求？继而如何求e(i)和和l(i)？(1) Ve计算从开始顶点向后递推。计算从开始顶点向后递推。Ve(j)的计算必须在的计算必须在vj的所有前驱顶的所有前驱顶点点vk的的Ve(k)全部计算出来以后才能全部计算出来以后才能进行进行。因此，可以在拓扑排序算法。因此，可以在拓扑排序算法中定义一个大小为中定义一个大小为n的数组的数组Ve,
19、Vej初值为初值为0。按照拓扑序列。按照拓扑序列求各顶点求各顶点vk的的Vek ，并利用，并利用Vek对对vk的每的每一后继顶点一后继顶点vj修正修正Vej。网采用邻。网采用邻接表，接表，给每个结点增加活动编号域给每个结点增加活动编号域active和活动持续时间域和活动持续时间域dut。(2) 同时同时设置一大小为设置一大小为m的数组的数组e，对每一事件对每一事件vj，可从邻接表中找到，可从邻接表中找到从从vj发出的每一条有向边发出的每一条有向边和边序号和边序号i，ei=Vej。(3)Vl计算从结束顶点开始向前递推。计算从结束顶点开始向前递推。 Vl(j)的计算必须在的计算必须在vj的所有后继
20、顶点的所有后继顶点的最迟发生时间全部计算出来以后才的最迟发生时间全部计算出来以后才能进行能进行。定义一个大小为。定义一个大小为n的数组的数组Vl,Vlj初值为初值为Ven。实际上。实际上,按照在按照在计算计算Ve时得到的时得到的 拓扑序列逆序拓扑序列逆序，依，依次计算各顶点次计算各顶点vk的的Vlk, 并并利用利用Vlk按照递推公式对按照递推公式对vk的每一个前驱顶点的每一个前驱顶点vj修正修正Vlj 。(4)设置一大小为设置一大小为m的数组的数组l，计算出，计算出Vl后，后，扫描每一个弧结点扫描每一个弧结点，得弧的终点，得弧的终点k、权和该弧序号、权和该弧序号i，li=Vlk- dut()。
21、AOE网的邻接表网的邻接表987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4AOE网网AOE网的存储结构网的存储结构采用邻接表采用邻接表1 02 13 14 15 26 17 18 29 2 data Id adj1612425264146 977 4 982108411415012345678353dest dut active next778给每个顶点增加域给每个顶点增加域Id，用于存放事件的入度，给每个边，用于存放事件的入度，给每个边增加增加两个域两个域dut和和active，用于存放活动的持续时间和活动的编号。，用于存放活动的
22、持续时间和活动的编号。987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4064577161418计算各事件最早发生时间计算各事件最早发生时间Ve和各活动最早开始时间和各活动最早开始时间e的过程的过程栈栈(底底-顶顶)拓扑拓扑序列序列v1 v2 v3 v4v5v6v7v8v90v10 0 0 0000003,2,1v20 6 4 5000003,2v30 6 4 56+1=700003,4v50 6 4 54+1=5 700003,6v70 6 4 5707+9=167+7=1403v40 6 4 570161416+2=185v60
23、6 4 575+2=71614187v80 6 4 577167+7=1414188v90 6 4 577161414+4=1818空空0 6 4 577161418 活动活动ai a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 e(j) 0 0 0 6 4 5 9 7 7 16 140645771614007事件事件j 1 2 3 4 5 6 7 8 9 Ve(j) 0 6 4 5 7 7 16 14 18前已求得拓扑序列为前已求得拓扑序列为,其其逆拓扑序列为逆拓扑序列为,置置Vl(9)=18,Vl(8)=Vl(9)-dut()=18-4=14Vl(6)=Vl(8)-d
24、ut()=14-4=10Vl(4)=Vl(6)-dut()=10-2=8Vl(7)= Vl(9)-dut()=18-2=16Vl(5)=minVl(7)-dut(), Vl(8)-dut()=7Vl(3)=Vl(5)-dut()=7-1=6Vl(2)=Vl(5)-)-dut(), Vl(3)-dut()=min0,2=0求得图中所求得图中所dut()=7-1=6Vl(1)=minVl(2有事件的最迟发生时间如下有事件的最迟发生时间如下:987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=40668710161418事件事件j 1 2 3
25、4 5 6 7 8 9 Vl(j) 0 6 6 8 7 10 16 14 18活动活动ai a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 l(i) 0 2 3 6 6 8 7 7 10 16 14 其中其中 l(i)=Vl(k) -dut() 06687101614732计算各事件最迟发生时间计算各事件最迟发生时间Vl和各活动最迟开始时间和各活动最迟开始时间l的过程的过程求得图中所有活动的最迟开始时间如下求得图中所有活动的最迟开始时间如下:n总结：求关键路径步骤总结：求关键路径步骤n1、求、求Ve(j)n2、求、求Vl(j)n3、求、求e(i)n4、求、求l(i)n5、
26、计算、计算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4v1v2v3v5v7v4v6v8v9顶点顶点 Ve Vl0647165714180667168101418a1a2a3a4a5a6a7a8a9a10a11活动活动 e l l-e Key Activity 000022660462583770770710316160141400331、2、3、4、5、n算法实现算法实现n以邻接表作存储结构以邻接表作存储结构n从源点从源点v1出发，令出发，令Ve0=0,按按拓扑序列拓扑序列求各顶点求各顶点的的Vejn从汇点从汇
27、点vn出发，令出发，令Vln-1=Ven-1,按按逆拓扑序列逆拓扑序列求其余各顶点的求其余各顶点的Vljn根据各顶点的根据各顶点的Ve和和Vl值，计算每条弧的值，计算每条弧的ei和和li,找出找出ei=li的关键活动的关键活动987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4n关键路径的讨论关键路径的讨论对于对于AOE网，我们所关心的有两个问题：网，我们所关心的有两个问题：1、完成整个工程的时间可由、完成整个工程的时间可由Ven求得求得2、关键活动（哪些活动的进度是影响整个工程进度的关键）、关键活动（哪些活动的进度是影响整个工程进度的
28、关键）在这里可以找到两条关键路径：在这里可以找到两条关键路径：a1、a4、a7、a10a1、a4、a8、a11 它们的路径长度都是它们的路径长度都是18987521a1=6a4=1a7=9a8=7a10=2a11=4如果一个活动处于所有的关键路径上，那么提高这个活动的如果一个活动处于所有的关键路径上，那么提高这个活动的速度，就能缩短整个工程的完成时间。如：速度，就能缩短整个工程的完成时间。如：a1、a4。但。但是，完成时间不能缩短太多，否则会使原来的关键路径是，完成时间不能缩短太多，否则会使原来的关键路径变成不是关键路径，这时，必须重新寻找关键路径。如：变成不是关键路径，这时，必须重新寻找关键
29、路径。如：a1由由6天变成天变成3天，就会改变关键路径。天，就会改变关键路径。作业作业15n概念题：概念题：n1、写出计算左图的拓、写出计算左图的拓扑序列的过程扑序列的过程n2、基于、基于1的结果计算左的结果计算左图的关键路径，写出计图的关键路径，写出计算过程算过程n程序设计题：程序设计题：n完成拓扑排序完成拓扑排序TopSort(G,Visit()函数，函数，实现按照图实现按照图G的拓扑序的拓扑序列访问图中顶点列访问图中顶点v1v2v4v5v8v10v7v6v3v9a1=3a2=2a3=6a4=3a5=8a6=4a7=2a8=7a9=4a10=6a11=9a12=6a13=5a14=4a15
30、=8第三次上机实习第三次上机实习全国铁路全国铁路运输网最佳经由问题运输网最佳经由问题n铁路运输网络中有铁路线和火车站两个铁路运输网络中有铁路线和火车站两个主要概念，譬如：主要概念，譬如：1号铁路线表示京广线，号铁路线表示京广线，2号铁路线表示京沪线等。号铁路线表示京沪线等。n铁路线对象包括铁路线编号、铁路线名称、铁路线对象包括铁路线编号、铁路线名称、起始站编号、终点站编号、该铁路线长度、起始站编号、终点站编号、该铁路线长度、通行标志（通行标志（00B客货运禁行，客货运禁行，01B货运通行货运通行专线，专线，10B客运通行专线，客运通行专线，11B客货运通行）客货运通行）。n火车站对象包括所属铁
31、路线编号、车站代码、火车站对象包括所属铁路线编号、车站代码、车站名、车站简称、离该铁路线起点站路程车站名、车站简称、离该铁路线起点站路程及终点站路程。及终点站路程。n要求：要求：n1）查询某站所属的铁路线。）查询某站所属的铁路线。n2）要求具备新增铁路线的管理功能。）要求具备新增铁路线的管理功能。n3）要求具备新增车站的管理功能。）要求具备新增车站的管理功能。n4）针对客运、货运情况能计算任何一个）针对客运、货运情况能计算任何一个起始车站到任何一个终点站之间的最短起始车站到任何一个终点站之间的最短路径。并且要求能够显示出该最短路径路径。并且要求能够显示出该最短路径的各个火车站的经由顺序。的各个火车站的经由顺序。
