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

1、第五章第五章 拓扑排序和关键路径拓扑排序和关键路径吉林大学计算机学院谷方明问题问题背景背景p计划、施工过程、生产流程、程序流程等都计划、施工过程、生产流程、程序流程等都可可以看作一个任务或以看作一个任务或“工程工程”。p除了很小的工程外，一般都把工程分为若干个除了很小的工程外，一般都把工程分为若干个叫做叫做“活动活动”的子的子任务任务。p活动之间一般会活动之间一般会有先后关系。如果不违反限制有先后关系。如果不违反限制完成这些活动，那么整个工程顺利完成完成这些活动，那么整个工程顺利完成。例：选课例：选课p计算机专业学生的学习就是一个工程，每一门计算机专业学生的学习就是一个工程，每一门课程的学习就

2、是整个工程的一课程的学习就是整个工程的一项项活动。其中有活动。其中有些课程要求先修课程，有些则不要求。这样在些课程要求先修课程，有些则不要求。这样在有的课程之间有先后关系，有的课程可以并行有的课程之间有先后关系，有的课程可以并行地学习。地学习。p任务：安排一种学习次序，使得所有课程都学任务：安排一种学习次序，使得所有课程都学习完成，并满足课程的限制关系。习完成，并满足课程的限制关系。计算机专业必修课程计算机专业必修课程课程代号课程代号 课程名称课程名称 先修课程先修课程 C0 高等数学高等数学 无无 C1 程序设计基础程序设计基础 无无 C2 离散数学离散数学 C0,C1 C3 数据结构数据结

3、构 C2,C4 C4 程序设计语言程序设计语言 C1 C5 编译技术编译技术 C3,C4 C6 操作系统操作系统 C3,C8 C7 普通物理普通物理 C0 C8 计算机原理计算机原理 C7 C0C2C3C5C4C1C7C6C8p在有向图中，用在有向图中，用顶点表示活动顶点表示活动，用，用有向边表示有向边表示活动之间的先后关系活动之间的先后关系，称这样的有向图为，称这样的有向图为AOV网网(Activity On Vertex Network)。p拓扑序列：拓扑序列：把把AOV网中的所有顶点排成一个网中的所有顶点排成一个线性序列，该序列满足如下条件：如果存在有线性序列，该序列满足如下条件：如果存

4、在有向边向边，则在该序列中，则在该序列中，Vi 必位于必位于Vj 之之前。前。p拓扑排序：拓扑排序：构造构造AOV网的拓扑序列的过程被网的拓扑序列的过程被称为拓扑排序。称为拓扑排序。p一种可能的拓扑序列是一种可能的拓扑序列是C0C2C3C5C4C1C7C6C8拓扑序列的存在性拓扑序列的存在性p任意任意AOV网中拓扑序列不一定存在网中拓扑序列不一定存在。例如，。例如，存在回路的存在回路的AOV网就网就无法找到拓扑序列。无法找到拓扑序列。因因为出现了有向环，则意味着某项活动应以自己为出现了有向环，则意味着某项活动应以自己作为先决条件。作为先决条件。p有有向向无环图无环图一定存在拓扑序列。一定存在拓

5、扑序列。构造方法构造方法p引理引理5.1： 设图设图G = (V, E)是有向无环图是有向无环图, V(G), 则则G中一定存在入度为零的顶点。中一定存在入度为零的顶点。p构造方法：构造方法： 从网中选择一个入度为从网中选择一个入度为0的顶点且输出之。的顶点且输出之。 从网中删除该顶点及其所有出边。从网中删除该顶点及其所有出边。 执行执行 ，直至所有顶点已输出，或网中剩余顶点，直至所有顶点已输出，或网中剩余顶点入度均不为入度均不为0 （说明网中存在回路）。（说明网中存在回路）。C0C2C3C5C4C1C7C6C8算法设计算法设计pAOV网用邻接表的形式存储网用邻接表的形式存储；p数组数组cou

6、nt ，counti的值是顶点的值是顶点i的入度；的入度；p使用一个使用一个数据结构数据结构，存放入度为，存放入度为0的点。的点。线性表存放时发生在一端；取用顺序无所谓，在同一端（栈）或另一端（队列）。栈的模拟栈的模拟p利用变量利用变量top和和count数组元素的值来模拟堆数组元素的值来模拟堆栈的压入和弹出。栈的压入和弹出。p原理：利用入度为原理：利用入度为0的的counti空间记录栈元空间记录栈元素的下标；素的下标；top始终记录栈顶元素的下标。始终记录栈顶元素的下标。拓扑排序算法拓扑排序算法算法算法TopoOrder( ) /* 图的拓扑排序算法，图的拓扑排序算法，n表示顶点数表示顶点数

7、 */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“有回路有回路! ”; RETURN; j

8、 = top , top = counttop . /* 弹出栈顶弹出栈顶j */ cout link) k = p - VerAdj ; countk - ;/ 顶点顶点k的入度减的入度减1 if (countk = 0 ) countk=top, top = k; 436251-111013124536counttop-112123124536counttop模拟栈的状态模拟栈的状态p初始化：初始化： top = -1;p栈栈 空：空： top = -1p入栈入栈：counti = top; top = i;p出栈出栈：j = top; top = counttop;算法分析算法分析p定理

9、定理5.2 设设G=(V, E)是有向无环图，是有向无环图，V(G)=1, 2 , n, e=|E(G)|. 则算法则算法TopoOrder是正确是正确的且算法的时间复杂性为的且算法的时间复杂性为 O(n+e).p正确性证明：正确性证明：初始化T1时，栈不为空T2时，如果G不空，栈也不空。输出n个顶点结束设是边，则 v 一定 排在 w 之前。拓展拓展p拓扑排序与有向环拓扑排序与有向环无回路的AOV网，其顶点可排成拓扑序列；有回路的AOV网，找不到所有顶点的拓扑序列；如果能将AOV网的所有顶点排成拓扑序列，则该AOV网中必定无有向环；如果得不到所有顶点的拓扑序列，则说明AOV网中存在有向环(AO

10、V网所代表的工程是不可行的)。p拓扑序列的个数拓扑序列的个数关键路径关键路径p时间约束时间约束p边表示活动边表示活动(Activity)p 边的权值表示活动的持续时间边的权值表示活动的持续时间(Duration)p 顶点表示入边的活动已完成，出边的活动可顶点表示入边的活动已完成，出边的活动可以开始的状态，也称为事件以开始的状态，也称为事件(Event)p这样的这样的有向无环带有向无环带权图叫做权图叫做AOE (Activity On Edges)网。网。例例 某工程某工程p源点：源点：表示整个工程的开始（入度为零）。表示整个工程的开始（入度为零）。p汇点：汇点：表示整个工程的结束（出度为零）。

11、表示整个工程的结束（出度为零）。p完成整个工程至少需要多少时间？完成整个工程至少需要多少时间？p为缩短工程的时间，应当加快哪些活动？为了不延误为缩短工程的时间，应当加快哪些活动？为了不延误整个工期，哪些活动不得延期，哪些可适当延期整个工期，哪些活动不得延期，哪些可适当延期436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2汇点汇点源点源点a6=1关键路径和关键活动关键路径和关键活动pAOE网中，有些活动可并行进行。只有各网中，有些活动可并行进行。只有各条路径上所有活动都完成了，整个工程才条路径上所有活动都完成了，整个工程才算完成。算完

12、成。p因此，完成整个工程所需的时间取决于从因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度。路径长度等源点到汇点的最长路径长度。路径长度等于路径上各边的权之和。这条具有最大长于路径上各边的权之和。这条具有最大长度的路径就叫做度的路径就叫做关键路径关键路径。p关键活动关键活动：不按期完成就会影响整个工期：不按期完成就会影响整个工期的活动。的活动。 p关键路径上的活动为关键活动；从源点到关键路径上的活动为关键活动；从源点到汇点由关键活动构成的路径为关键路径。汇点由关键活动构成的路径为关键路径。436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a

13、12=4a11=2汇点汇点源点源点a6=1关键活动有关的量关键活动有关的量 事件事件vj的最早发生时间的最早发生时间 ve( j ): 从源点从源点v0到到vj的最长路径长度。的最长路径长度。436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2汇点汇点源点源点a6=1ve(1)=0ve(2)= 6ve(3)= 4ve(4)= 5ve(5)= 7ve(6)= 7ve(7)= 16ve(8)= 15ve(9)= 19 事件事件vj的最迟发生时间的最迟发生时间 vl ( j ): 保证汇点的最早发生时间不推保证汇点的最早发生时间不推迟的前提

14、下，事件迟的前提下，事件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 ai i的最早开始时间的最早开始时间e(ie(i):): 设活动设活动a ai i为有向边为有向边 ，则，则 e(ie(i) =

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

16、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)= 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 0 0 0 6 6 4 4 5 7 4 4 5 7 7 7 7 7 16 16 1515 0 0 2 4 2 4 6 6 6 10 9 8 6 10 9 8 7 7 1

17、111 17 17 1515 0 0 2 2 2 2 0 0 2 5 3 1 2 5 3 1 0 0 4 0 4 0 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(i) 与与 l(i)，需要先求得从源点，需要先求得从源点V0到各个顶点到各个顶点Vj 的的 ve(j) 和和 vl(j)。436

18、251978a1=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是关键活动。是关键

19、活动。 例例 求关键活动求关键活动 第第1步步ve(k) ve(k)ve(1)0 k=1maxve(j)+ weight() E(G), k=2, 3, , n436251978a1=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)+ weig

20、ht()， ve(4)+ weight()=max4+1,5+3=7ve(7)= ve(4)+weight()=7+9=16ve(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),

21、j= n-1, n-2,1436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=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() =mi

22、n11-1,7-1=6vl(2)= vl(5)-weight()=7-1=6vl(1)= minvl(2)- weight()， vl(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步步pe(i)=ve(j), l(i)=vl(k)-weight()aie(i)l(i)li-ei 0 0 0 0 0 0 6 6 4 4 5 7 4 4 5 7 7 7 7 7 16 16 1515 0 0 2

23、4 2 4 6 6 6 10 9 8 6 10 9 8 7 7 1111 17 17 1515 0 0 2 2 2 2 0 0 2 5 3 1 2 5 3 1 0 0 4 0 4 0 0 0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12436251978a1=6a9=8a8=9a7=2a4=1a5=1a3=5a2=4a10=4a12=4a11=2汇点汇点源点源点a6=1图的关键路径算法图的关键路径算法 算法算法CriticalPath ( )/* 图的关键路径算法图的关键路径算法 */CPath1计算事件的最早发生时间计算事件的最早发生时间 for ( i =

24、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求诸活动的最早开始时间和最迟开始时间求诸活动的最早开始时间和最迟开始时间 for ( i = 1 ; i link) k =p - VerAdj ； e = vei ; l = v