数据结构,拓扑排序和关键路径课件

1、第五章 拓扑排序和关键路径吉林大学计算机学院谷方明fmgu2002问题背景计划、施工过程、生产流程、程序流程等都可以看作一个任务或“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子任务。活动之间一般会有先后关系。如果不违反限制完成这些活动，那么整个工程顺利完成。例：选课计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一项活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有先后关系，有的课程可以并行地学习。任务：安排一种学习次序，使得所有课程都学习完成，并满足课程的限制关系。计算机专业必修课程课程代号 课程名称 先修课程 C0 高等数学 无 C1 程

2、序设计基础 无 C2 离散数学 C0,C1 C3 数据结构 C2,C4 C4 程序设计语言 C1 C5 编译技术 C3,C4 C6 操作系统 C3,C8 C7 普通物理 C0 C8 计算机原理 C7 C0C2C3C5C4C1C7C6C8在有向图中，用顶点表示活动，用有向边表示活动之间的先后关系，称这样的有向图为AOV网(Activity On Vertex Network)。拓扑序列：把AOV网中的所有顶点排成一个线性序列，该序列满足如下条件：如果存在有向边，则在该序列中，Vi 必位于Vj 之前。拓扑排序：构造AOV网的拓扑序列的过程被称为拓扑排序。一种可能的拓扑序列是：C0 , C1 , C

3、2 , C4 , C3 , C5 , C7 , C8 , C6C0C2C3C5C4C1C7C6C8拓扑序列的存在性任意AOV网中拓扑序列不一定存在。例如，存在回路的AOV网就无法找到拓扑序列。因为出现了有向环，则意味着某项活动应以自己作为先决条件。有向无环图一定存在拓扑序列。构造方法引理5.1： 设图G = (V, E)是有向无环图, V(G), 则G中一定存在入度为零的顶点。构造方法： 从网中选择一个入度为0的顶点且输出之。 从网中删除该顶点及其所有出边。执行 ，直至所有顶点已输出，或网中剩余顶点入度均不为0 （说明网中存在回路）。C0 , C1 , C2 , C4 , C3 , C5 ,

4、C7 , C8 , C6C0 , C1 , C4 , C2 , C3 , C5 , C7 , C8 , C6C0 , C1 , C7 , C2 , C4 , C3 , C5 , C8 , C6C0C2C3C5C4C1C7C6C8算法设计AOV网用邻接表的形式存储；数组count ，counti的值是顶点i的入度；使用一个数据结构，存放入度为0的点。线性表存放时发生在一端；取用顺序无所谓，在同一端（栈）或另一端（队列）。栈的模拟利用变量top和count数组元素的值来模拟堆栈的压入和弹出。原理：利用入度为0的counti空间记录栈元素的下标；top始终记录栈顶元素的下标。拓扑排序算法算法Topo

5、Order( ) /* 图的拓扑排序算法，n表示顶点数 */T1初始化 for( i = 1 ; i= n ; i + ) counti = 0; for( i = 1 ; ilink ) count p-VerAdj +; for( i = 1 ; i= n ; i + ) if( counti = 0 ) counti = top , top = i ;002123124536count436251toptop-102123124536count-112123124536countT2拓扑排序 for( i = 1 ; i = n ; i+ ) if ( top = - 1 ) cout“

6、有回路! ”; RETURN; j = top , top = counttop . /* 弹出栈顶j */ cout link) k = p - VerAdj ; countk - ;/ 顶点k的入度减1 if (countk = 0 ) countk=top, top = k; 436251-111013124536counttop-112123124536counttop模拟栈的状态初始化： top = -1;栈 空： top = -1入栈：counti = top; top = i;出栈：j = top; top = counttop;算法分析定理5.2 设G=(V, E)是有向无环图

7、，V(G)=1, 2 , n, e=|E(G)|. 则算法TopoOrder是正确的且算法的时间复杂性为 O(n+e).正确性证明：初始化T1时，栈不为空T2时，如果G不空，栈也不空。输出n个顶点结束设是边，则 v 一定 排在 w 之前。拓展拓扑排序与有向环无回路的AOV网，其顶点可排成拓扑序列；有回路的AOV网，找不到所有顶点的拓扑序列；如果能将AOV网的所有顶点排成拓扑序列，则该AOV网中必定无有向环；如果得不到所有顶点的拓扑序列，则说明AOV网中存在有向环(AOV网所代表的工程是不可行的)。拓扑序列的个数关键路径时间约束边表示活动(Activity) 边的权值表示活动的持续时间(Dura

8、tion) 顶点表示入边的活动已完成，出边的活动可以开始的状态，也称为事件(Event)这样的有向无环带权图叫做AOE (Activity On Edges)网。例 某工程源点：表示整个工程的开始（入度为零）。汇点：表示整个工程的结束（出度为零）。完成整个工程至少需要多少时间？为缩短工程的时间，应当加快哪些活动？为了不延误整个工期，哪些活动不得延期，哪些可适当延期436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2汇点源点a6=1关键路径和关键活动AOE网中，有些活动可并行进行。只有各条路径上所有活动都完成了，整个工程才算完成。因此，

9、完成整个工程所需的时间取决于从源点到汇点的最长路径长度。路径长度等于路径上各边的权之和。这条具有最大长度的路径就叫做关键路径。关键活动：不按期完成就会影响整个工期的活动。 关键路径上的活动为关键活动；从源点到汇点由关键活动构成的路径为关键路径。436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2汇点源点a6=1关键活动有关的量 事件vj的最早发生时间 ve( j ): 从源点v0到vj的最长路径长度。436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2汇点源点a6=1ve(1

10、)=0ve(2)= 6ve(3)= 4ve(4)= 5ve(5)= 7ve(6)= 7ve(7)= 16ve(8)= 15ve(9)= 19 事件vj的最迟发生时间 vl ( j ): 保证汇点的最早发生时间不推迟的前提下，事件vj允许的最迟开始时间，等于ve(n)减去从vj到vn最长路径长度。436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2汇点源点a6=1vl(9)= 19vl(8)= 15vl(7)= 17vl(6)= 11vl(5)= 7vl(4)= 9vl(3)= 6vl(2)= 6vl(1)= 0关键活动有关的量 活动a

11、i的最早开始时间e(i): 设活动ai为有向边，则 e(i) = ve(j)。 ve(j)是从源点v0到vj的最长路径长度，决定了所有从vj开始的活动的最早开始时间。 活动ai的最迟开始时间 l(i): l(i) 是在不会引起工期延误的前提下，该活动允许的最迟开始时间。设活动ai为有向边, 则 l(i) = vl(k)-weight()。vl(9)= 19vl(8)= 15vl(7)= 17vl(6)= 11vl(5)= 7vl(4)= 9vl(3)= 6vl(2)= 6vl(1)= 0ve(1)=0ve(2)= 6ve(3)= 4ve(4)= 5ve(5)= 7ve(6)= 7ve(7)=

12、16ve(8)= 15ve(9)= 19436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2a6=1aie(i)l(i)li-ei 0 0 0 6 4 4 5 7 7 7 16 15 0 2 4 6 6 10 9 8 7 11 17 15 0 2 2 0 2 5 3 1 0 4 0 0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 关键活动： l(i) e(i) 表示活动ak 是没有时间余量的关键活动。为找出关键活动, 需要求各个活动的 e(i) 与 l(i)，以判别是否 l(i) e(i) 为求得e(

13、i) 与 l(i)，需要先求得从源点V0到各个顶点Vj 的 ve(j) 和 vl(j)。436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2汇点源点a6=1求关键活动算法 对AOE网拓扑排序;（若网中有回路，则终止算法） 按拓扑次序求出各顶点事件的最早发生时间ve; 按拓扑序列的逆序求各顶点事件的最迟发生时间vl; 根据ve和vl的值，求各活动的最早开始时间e(i)与最迟开始时间l(i)，若e(i)=l(i)，则i是关键活动。 例 求关键活动 第1步ve(k) ve(k)ve(1)0 k=1maxve(j)+ weight() E(G

14、), k=2, 3, , n按拓扑正序递推:436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2汇点源点a6=1ve(1)=0ve(2)= ve(1)+weight()=6ve(3)= ve(1)+weight()=4ve(4)= ve(1)+weight()=5ve(5)= maxve(2)+ weight()， ve(3)+ weight()=max6+1,4+1=7ve(6)= maxve(3)+ weight()， ve(4)+ weight()=max4+1,5+3=7ve(7)= ve(4)+weight()=7+9=16

15、ve(8)= maxve(4)+ weight()， ve(5)+ weight()=max7+8,7+4=15ve(9)= maxve(6)+ weight()， ve(7)+ weight()=max16+2,15+4=19436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2a6=1例 求关键活动 第2步vl(k) vl(j)ve(n) j=nminvl(k)- weight() E(G), j= n-1, n-2,1按拓扑逆序递推:436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12

16、=4a11=2汇点源点a6=1vl(9)= ve(9)=19vl(8)= vl(9)-weight()=15vl(7)= vl(9)-weight()=17vl(6)= vl(8)-weight()=11vl(5)= minvl(8)- weight()， vl(7)- weight() =min15-8,16-9=7vl(4)= vl(6)-weight()=11-2=9vl(3)= minvl(6)- weight()， vl(5)- weight() =min11-1,7-1=6vl(2)= vl(5)-weight()=7-1=6vl(1)= minvl(2)- weight()， v

17、l(3)- weight(), vl(4)- weight() = min6-6,6-4,9-5=0436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2a6=1例 求关键活动 第3步e(i)=ve(j), l(i)=vl(k)-weight()aie(i)l(i)li-ei 0 0 0 6 4 4 5 7 7 7 16 15 0 2 4 6 6 10 9 8 7 11 17 15 0 2 2 0 2 5 3 1 0 4 0 0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12436251978a1=6a9=

18、8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2汇点源点a6=1图的关键路径算法 算法CriticalPath ( )/* 图的关键路径算法 */CPath1计算事件的最早发生时间 for ( i = 1 ; i = n ; i + ) ve i = 0; for ( i = 2 ; i link) k =p - VerAdj ； if (vei + p - cost vek ) vek =vei + p - cost ; CPath2计算事件的最迟发生时间 for ( i = 1 ; i = 1 ; i - ) /*按拓扑逆序*/ for ( p = Head i . adjacent ; p ; p = p- link) k =p - VerAdj ； if (vlk p- cost cost ;CPath3求诸活动的最早开始时间和最迟开始时间 fo