《第16讲拓扑排序与关键路径概要》由会员分享，可在线阅读，更多相关《第16讲拓扑排序与关键路径概要（35页珍藏版）》请在金锄头文库上搜索。
1、第十六讲 拓扑排序与关键路径,主讲：朱郑州,数据结构 Data Structure,主要内容,1. 拓扑排序,2. 关键路径,AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。,什么是工程？工程有什么共性？,AOV网中出现回路意味着什么？,AOV网,AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。,什么是工程？工程有什么共性？,AOV网,AOV网,拓扑序列：设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1, v2, , vn
2、称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。 拓扑排序：对一个有向图构造拓扑序列的过程称为拓扑排序 。,拓扑序列使得AOV网中所有应存在的前驱和后继关系都能得到满足。,拓扑排序,基本思想： 从AOV网中选择一个没有前驱的顶点并且输出； 从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧； 重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。,拓扑排序的结果？,拓扑排序,拓扑序列：,C1,C2,C3,C4,C5,C6,C7,拓扑排序,拓扑排序,设计数据结构,1. 图的存储结构：采用邻接表存储 ，在顶点表中增加一
3、个入度域。 顶点表结点,2. 栈S：存储所有无前驱的顶点。,拓扑排序,(a) 一个AOV网 (b) AOV网的邻接表存储,0 1 2 3 4 5,in vertex firstedge,3 A 0 B 1 C 3 D 0 E 2 F ,0,3 ,0,0,5 ,2,3 ,3,5 ,拓扑排序,0 1 2 3 4 5,in vertex firstedge,3 A 0 B 1 C 3 D 0 E 2 F ,0,3 ,0,0,5 ,2,3 ,3,5 ,B,E,拓扑排序,0 1 2 3 4 5,in vertex firstedge,3 A 0 B 1 C 3 D 0 E 2 F ,0,3 ,0,0,5
4、 ,2,3 ,3,5 ,B,E,0,C,2,1,拓扑排序,0 1 2 3 4 5,in vertex firstedge,3 A 0 B 0 C 2 D 0 E 1 F ,0,3 ,0,0,5 ,2,3 ,3,5 ,B,C,2,1,拓扑排序,0 1 2 3 4 5,in vertex firstedge,2 A 0 B 0 C 1 D 0 E 1 F ,0,3 ,0,0,5 ,2,3 ,3,5 ,B,D,0,1,拓扑排序,0 1 2 3 4 5,in vertex firstedge,1 A 0 B 0 C 0 D 0 E 1 F ,0,3 ,0,0,5 ,2,3 ,3,5 ,0,0,A,F,
5、拓扑排序,0 1 2 3 4 5,in vertex firstedge,0 A 0 B 0 C 0 D 0 E 0 F ,0,3 ,0,0,5 ,2,3 ,3,5 ,A,F,拓扑排序,1. 栈S初始化；累加器count初始化； 2. 扫描顶点表，将没有前驱的顶点压栈； 3. 当栈S非空时循环 3.1 vj=退出栈顶元素；输出vj；累加器加1； 3.2 将顶点vj的各个邻接点的入度减1； 3.3 将新的入度为0的顶点入栈； 4. if (countvertexNum) 输出有回路信息；,拓扑排序算法伪代码,拓扑排序,主要内容,1. 拓扑排序,2. 关键路径,AOE网：在一个表示工程的带权有向图
6、中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE网。AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。,AOE网的性质： 只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始； 只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。,AOE网,事件 事件含义 v1 开工 v2 活动a1完成，活动a4可以开始 v3 活动a2完成，活动a5可以开始 v9 活动a10 和a11完成，整个工程完成,AOE网,AOE网可以回答下列问题： 1. 完成整个工程至少需要多少时间? 2. 为缩短完成工程所需
7、的时间, 应当加快哪些活动?,从始点到终点的路径可能不止一条，只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的最短时间取决于从始点到终点的最长路径长度，即这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径。,AOE网,关键路径：在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。 关键活动：关键路径上的活动称为关键活动。,由于AOE网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期。,关键路径,要找出关键路径，必须找出关键活动
8、, 即不按期完成就会影响整个工程完成的活动。,首先计算以下与关键活动有关的量：, 事件的最早发生时间vek 事件的最迟发生时间vlk 活动的最早开始时间ei 活动的最晚开始时间li,最后计算各个活动的时间余量 lk - ek，时间余量为0者即为关键活动。,关键路径,vek是指从始点开始到顶点vk的最大路径长度。这个长度决定了所有从顶点vk发出的活动能够开工的最早时间。,ve1=0 vek=maxvej+len (pk) pk表示所有到达vk的有向边的集合, 事件的最早发生时间vek,关键路径,vek,0,6,4,5,7,7,16,14,18,vek=maxvej+len,关键路径,vlk是指在
9、不推迟整个工期的前提下,事件vk允许的最晚发生时间。, 事件的最迟发生时间vlk,vln=ven vlk=minvlj-len（sk） sk为所有从vk发出的有向边的集合,关键路径,vek,vlk,0,6,4,5,7,7,16,14,18,18,14,16,10,7,8,6,6,0,vlk=minvlj-len,关键路径, 活动的最早开始时间ei,若活动ai是由弧表示，则活动ai的最早开始时间应等于事件vk的最早发生时间。因此，有： ei=vek,关键路径,vek,0,6,4,5,7,7,16,14,18,a2,a7,a6,a5,a4,a1,a3,a9,a8,ei,0,0,0,6,4,5,7,
10、7,7,a10,a11,16,14,ei=vek,关键路径,活动ai的最晚开始时间是指，在不推迟整个工期的前提下， ai必须开始的最晚时间。 若ai由弧表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此，有： li=vlj-len, 活动的最晚开始时间li,vlk,18,14,16,10,7,8,6,6,0,关键路径,li,10,7,7,8,6,6,3,2,0,16,14,a2,a7,a6,a5,a4,a1,a3,a9,a8,a10,a11,vlk,18,14,16,10,7,8,6,6,0,li=vlj-len,关键路径,a2,a7,a6,a5,a4,a1,a3,a9,a8,ei,li,0,0,0,6,4,5,7,7,7,10,7,7,8,6,6,3,2,0,a10,a11,16,14,16,14,v2,v1,v3,v4,v5,v8,v6,v7,v9,a1=6,a4=1,a7=9,a10=2,a11=4,a8=7,a9=4,a5=1,a6=2,a3=5,a2=4,关键活动：li=ei的活动,关键路径,课堂练习：求u0到其他各顶点的最短路径。,关键路径,关键路径,
