数据结构拓扑排序课件

1、数 据 结 构 DATA STRUCTURE, DS 拓扑排序数据结构课程内容图结构的应用3 拓扑排序图结构的应用4 关键路径8.7 拓扑排序（topological sort）先决条件问题拓扑排序将一个有向无环图中所有顶点在不违反先决条件关系的前提下排成线性序列的过程称为拓扑排序学生选修课程问题：学生应按怎样的顺序学习下列课程，才能无矛盾、顺利地完成学业？课程代号课程名称 先修课C1程序设计基础无C2离散数学C1C3数据结构C1,C2C4汇编语言C1C5语言的设计和分析C3,C4C6计算机原理C11C7编译原理C3.C5C8操作系统C3,C6C9高等数学无 C10线性代数C9C11普通物理C

2、9C12数值分析C1,C9,C10C1C2C3C4C5C6C7C8C9C10C11C12数学模型：有向无环图顶点活动（课程）有向弧活动i是活动j的先决条件序列1：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8序列2：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8Activity OnVertex network8.7 拓扑排序（续）拓扑序列(Topological order)对于有向无环图G=(V, E), 所有顶点组成的线性序列如果满足若在有向无环图G中从顶点Vi到Vj有一条路径，则在序列中顶点Vi必在顶点Vj之前则该线性序列可称

3、作一个拓扑序列。拓扑序列不唯一8.7 拓扑排序（续）任何有向无环图G的所有顶点都可以排在一个拓扑序列里。拓扑排序的方法是：1、从图G中选择一个入度为0的顶点并输出。2、从图G中删掉此顶点及其所有的出边。3、回到第1步继续执行，直至G所有顶点都被输出或G中不存在入度为0的顶点。C1C2C3C4C5C6C7C8C9C10C11C12C2C3C4C5C6C7C8C9C10C11C12（1）拓扑序列：C1C3C4C5C6C7C8C9C10C11C12（2）拓扑序列：C1-C2C4C5C6C7C8C9C10C11C12（3）拓扑序列：C1-C2-C3C5C6C7C8C9C10C11C12（4）拓扑序列：

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（10）拓扑序列：C1-C2-C3-C4 -C5-C7-C9-C10-C11-C6C8（11）拓扑序列：C1-C2-C3-C4 -C5-C7-C9-

5、C10-C11-C6 -C12（12）拓扑序列：C1-C2-C3-C4 -C5-C7-C9-C10-C11-C6 -C12-C8拓扑排序算法首先需要计算各顶点的入度，然后在拓扑排序过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有直接后继顶点的入度减1。为了避免重复检测入度为零的顶点，设立一个栈（或队列），以保存当前所有“入度为零”的顶点若有向G中所有顶点都被输出，则表明G中没有有向环，拓扑排序成功。若仅输出了部分顶点，G中已不存在入度为0的顶点，则表明G中存在有向环，拓扑排序失败。拓扑排序算法实现：设图G的顶点数为n1、对各顶点求入度2、初始化栈S3、把所有入度为0的顶点入栈

6、S4、当栈S非空时循环4.1 访问栈顶元素v并出栈；4.2 获得所有与v邻接的未被访问的顶点w4.3 把w的入度减1；4.4 若w的入度为0则入栈S直至栈S空为止5、如果存在顶点未被访问，则有向图有环，不存在拓扑序列，拓扑排序失败；否则，拓扑排序成功6、结束987645321123456789 data adjhead12546 7 8840123456783dest next7栈(底-顶)拓扑序列0v13,2,1v23,2v33,4v53,6v73v45v67v88v9空例如：8.7 拓扑排序（续）拓扑排序算法的时间复杂度分析关键是，算法在开始时要找出所有入度为0的顶点（同时可知道其它顶点的

7、入度）当采用邻接矩阵时，算法在开始时找所有入度为0的顶点需要 O (n2)的时间，加上处理边、顶点的时间，总代价为O(n2+e+n)= O (n2)当采用邻接表时，因为在顶点表的每个顶点中可以有一个字段来存储入度，所以算法在开始时找所有入度为0的顶点只需要O(e)的时间，加上处理边、顶点的时间，总代价为O(n+2e)=O(n+e)工程计划有关问题把工程计划表示为有向无环图G，用顶点表示事件，弧表示活动，权表示活动持续时间。每个事件表示在它之前的活动已完成，在它之后的活动可以开始（约束条件）例：设一个工程有m=11项活动，n=9个事件，其中事件vj 事件v1表示整个工程开始(记为v) 事件v9表

8、示整个工程结束(记为vn) 活动ai用弧表示，其持续时间记为dut()问题：（1）完成整项工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键活动？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=48.8 关键路径定义1AOE网(Activity On Edge network, 边表示活动的网)是一个顶点表示事件，弧表示活动，权表示活动持续时间的带权有向无环图。网中仅存在一个入度为0的顶点，称作开始顶点；网中仅存在一个出度为0的顶点，称为结束顶点距离路径上各活动持续时间之和关键路径从开始顶点到结束顶点的距离最长的路径 由于AO

9、E网中某些活动可以同时进行，要保证每个活动都能无矛盾顺利完成(约束条件)，完成该工程的最少时间就是该工程AOE网的关键路径距离。987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4定义2Ve(j)表示事件vj的最早(early)发生时间，是从开始顶点v到vj的最长路径距离。其中Ve(n)是该工程AOE网的关键路径距离。?如何计算Vl(j)表示事件vj的最迟(last)发生时间，是在不推迟整个工程完成(即保证结束顶点vn在Ve(n)时刻发生)的前提下,该事件最迟必须发生的时间。Vl(j)=Ve(n) 顶点vj到结束顶点vn的最长路径距离。

10、？如何计算987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4064577161418987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4Ve示例0668710161418Vl示例定义3e(i)表示活动ai的最早(early)开始时间，是该活动的起点所表示事件的最早发生时间如果边表示活动ai，则有e(i)=Ve(j)l(i)表示活动ai的最迟(last)开始时间，是该活动的终点所表示事件的最迟发生时间与该活动的所需时间之差如果边表示活动ai，则有l(i)=Vl(k)-dut()9

11、87645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=40645771614007e示例06687101614732l示例0645771614180668710161418vjvkai定义4l(i)-e(i)表示完成活动ai的时间余量，它是在不增加完成整个工程所需时间的情况下，活动ai可以拖延的时间关键活动关键路径上的活动，即l(i)=e(i)的活动987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9

12、=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关键路径如何找e(i)=l(i)的关键活动？设事件数为n，活动数为m。活动ai用弧表示，其持续时间记为dut()，则有：（1）e(i)=Ve(j)（2）l(i)=Vl(k) -dut()vjvkai如何求Ve(j)和Vl(j)？继而如何求e(i)和l(i)？(1) Ve计算从开始顶点向后递

13、推。Ve(j)的计算必须在vj的所有前驱顶点vk的Ve(k)全部计算出来以后才能进行。因此，可以在拓扑排序算法中定义一个大小为n的数组Ve, Vej初值为0。按照拓扑序列求各顶点vk的Vek ，并利用Vek对vk的每一后继顶点vj修正Vej。网采用邻接表，给每个结点增加活动编号域active和活动持续时间域dut。(2) 同时设置一大小为m的数组e，对每一事件vj，可从邻接表中找到从vj发出的每一条有向边和边序号i，ei=Vej。(3)Vl计算从结束顶点开始向前递推。 Vl(j)的计算必须在vj的所有后继顶点的最迟发生时间全部计算出来以后才能进行。定义一个大小为n的数组Vl,Vlj初值为Ven

14、。实际上,按照在计算Ve时得到的 拓扑序列逆序，依次计算各顶点vk的Vlk, 并利用Vlk按照递推公式对vk的每一个前驱顶点vj修正Vlj 。(4)设置一大小为m的数组l，计算出Vl后，扫描每一个弧结点，得弧的终点k、权和该弧序号i，li=Vlk- dut()。AOE网的邻接表987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4AOE网AOE网的存储结构采用邻接表102131415261718292 data Id adj1612425264146 977 4 982108411415012345678353dest dut activ

15、e next778给每个顶点增加域Id，用于存放事件的入度，给每个边增加两个域dut和active，用于存放活动的持续时间和活动的编号。987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4064577161418计算各事件最早发生时间Ve和各活动最早开始时间e的过程栈(底-顶)拓扑序列v1v2v3v4v5v6v7v8v90v10000000003,2,1v20645000003,2v306456+1=700003,4v506454+1=5 700003,6v70645707+9=167+7=1403v4064570161416+2=18

16、5v6064575+2=71614187v8064577167+7=1414188v9064577161414+4=1818空064577161418 活动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)-dut()=14-4=10Vl(4)=Vl(6)-dut()

17、=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 4 5 6 7 8 9 Vl(j) 0 6 6 8 7 10 16 14 18活动ai a1 a

18、2 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的过程求得图中所有活动的最迟开始时间如下:总结：求关键路径步骤1、求Ve(j)2、求Vl(j)3、求e(i)4、求l(i)5、计算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4v1v2v3v5v7v4v6v8v9顶点 Ve Vl0647165714180667168101418

19、a1a2a3a4a5a6a7a8a9a10a11活动 e l l-e Key Activity000022660462583770770710316160141400331、2、3、4、5、算法实现以邻接表作存储结构从源点v1出发，令Ve0=0,按拓扑序列求各顶点的Vej从汇点vn出发，令Vln-1=Ven-1,按逆拓扑序列求其余各顶点的Vlj根据各顶点的Ve和Vl值，计算每条弧的ei和li,找出ei=li的关键活动987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4关键路径的讨论对于AOE网，我们所关心的有两个问题：1、完成整个工程的时间可由Ven求得2、关键活动（哪些活动的进度是影响整个工程进度的关键）在这里可以找到两条关键路径：a1、a4、a7、a10a1、a4、a8、a11 它们的路径长度都是1898