第16讲拓扑排序和关键路径ppt课件

1、 一、拓扑排序一、拓扑排序 二、关键路径二、关键路径（a有向树有向树 （b有向无环图有向无环图 （c有向图有向图问题：判断一个有向图是否为有向无环图的方法是？问题：判断一个有向图是否为有向无环图的方法是？ 应用：应用： 工程流程、生产过程中各道工序的流程、程序工程流程、生产过程中各道工序的流程、程序流程、课程的流程。流程、课程的流程。 对整个工程和系统，人们关心的问题是：对整个工程和系统，人们关心的问题是：（1工程能否顺利进行工程能否顺利进行, ，即工程流程是否，即工程流程是否“合理合理”； （2完成整项工程至少需要多少时间，哪些子工程是影响完成整项工程至少需要多少时间，哪些子工程是影响工程进

2、度的关键子工程。工程进度的关键子工程。（1拓扑排序拓扑排序 （2关键路径关键路径 AOV网网( activity on vertex network ) 用顶点表示活动，边表示活动的顺序关系用顶点表示活动，边表示活动的顺序关系。 为求解工程流程是否为求解工程流程是否“合理合理”，通常用，通常用AOVAOV网的网的有向图表示工程流程。有向图表示工程流程。 某工程可分为某工程可分为6 6个子工程，若用顶点表示子工程也称活个子工程，若用顶点表示子工程也称活动）动）, , 用弧表示子工程间的顺序关系。用弧表示子工程间的顺序关系。 工程流程可用如下工程流程可用如下AOVAOV网表示：网表示：例例 ( (

3、开场开场) A ) A F ( F (完毕完毕) ) 5 5 6 6 6 6 7 7 4 4 4 4 5 5 1 1 3 3 B B E E D D C C 例例 2: 2: 计算机专业学生的学习就是一个工程，每一门计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。系，有的课程可以并行地学习。例例c1c1c2c2c3c3c4c4c5c5c6c6c7c7C8C8c9c9c10c10

4、c11c11c12c12程序设计程序设计离散数学离散数学数据结构数据结构汇编语言汇编语言算法分析算法分析计算机体系计算机体系编译方法编译方法操作系统操作系统高等数学高等数学线性代数线性代数电子电路电子电路数值分析数值分析无无 c1c1c1,c2c1,c2c1c1c3,c4c3,c4c11c11c5,c3c5,c3c3,c6c3,c6无无c9c9c9c9c9,c10,c1c9,c10,c1课程编号课程编号 课程名称课程名称 先决条件先决条件 c4c1c2c3c12c9c10c11c6c7c8c5如何安排施工计划？如何安排施工计划？如何安排教学计划？如何安排教学计划？ 一个可行的施工计划为：A,B

5、,C, D,E,F 一个可行的学习计划为：C1,C9,C4,C2,C10,C11,C12,C3,C6,C5,C7,C8 可行的计划的特点：若在流程图中顶点v是顶点u 的前趋，则在计划序列中顶点v 也是u的前趋。拓扑排序拓扑排序(TopologicalSort)(TopologicalSort) 按照有向图给出的次序关系，将图中顶点排按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系系的顶点，则可以人为加上任意的次序关系 由此所得顶点的线性序列称之为拓扑由此所得顶点的线性序列称之为拓扑有

6、序序列有序序列例如：对于下列有向图例如：对于下列有向图BDAC可求得拓扑有序序列：可求得拓扑有序序列： A B C D 或或 A C B DBDAC反之，对于下列有向图反之，对于下列有向图不能求得它的拓扑有序序列。不能求得它的拓扑有序序列。因为图中存在一个回路因为图中存在一个回路 B, C, DC1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：开场拓扑序列：开场（0）C2C3C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1（1）C3C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1-C2（2）C4C5C6C7C8C9C10C11C12拓扑序列：拓

7、扑序列：C1-C2-C3（3）C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1-C2-C3-C4（4）C6C8C10C11C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9C6C8C11C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10（8）C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5（5）C6C8C9C10C11C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7（6）（7）C6C8C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11（9）C8C12拓扑序列：

8、拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6（10）C8拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6-C12（11）拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9 -C10-C11-C6-C12-C8（12）C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8一个一个AOV网的拓扑序列不是唯一的网的拓扑序列不是唯一的如何在计算机上实

9、现如何在计算机上实现对有向图的拓扑排序？对有向图的拓扑排序？abcghdfeabhcdgfe（1） 选择一入度为选择一入度为 0 顶点顶点 v，输出；，输出；（2） 将将 v 邻接到的顶点的入度减邻接到的顶点的入度减1；（3） 重复重复12，直到输出全部顶点或图中没有入度为，直到输出全部顶点或图中没有入度为0的顶点；的顶点； 拓扑排序涉及的数据和操作：拓扑排序涉及的数据和操作： 数据：有向图，顶点的入度；数据：有向图，顶点的入度； 操作：（操作：（1） 选择一入度为选择一入度为 0 顶点顶点v，输出；，输出； （2） 将将 v 邻接到的顶点邻接到的顶点 u 的入度减的入度减1； 1. 图的存储

10、结构：采用邻接表存储图的存储结构：采用邻接表存储 ，在顶点，在顶点表中增加一个入度域。表中增加一个入度域。 顶点表结点顶点表结点 in vertexfirstedge2. 栈栈S：存储所有无前驱的顶点。：存储所有无前驱的顶点。考虑：可以用队列吗？考虑：可以用队列吗？(a) 一个一个AOV网网 (b) AOV网的邻接表存储网的邻接表存储 012345 in vertex firstarc3 A 0 B1 C3 D0 E2 F 0 3 0 0 5 2 3 3 5 ABCDEF拓扑排序拓扑排序拓扑排序拓扑排序012345 in vertex firstarc 3 A 0 B 1 C 3 D 0 E

11、2 F 0 3 0 0 5 2 3 3 5 ABCDEFBE拓扑排序拓扑排序012345 in vertex firstarc 3 A 0 B 1 C 3 D 0 E 2 F 0 3 0 0 5 2 3 3 5 ABCDEFBE0C21拓扑排序拓扑排序012345 in vertex firstarc 3 A 0 B 0 C 2 D 0 E 1 F 0 3 0 0 5 2 3 3 5 ABCDFBC21拓扑排序拓扑排序012345 in vertex firstarc 2 A 0 B 0 C 1 D 0 E 1 F 0 3 0 0 5 2 3 3 5 ABDFB D01拓扑排序拓扑排序0123

12、45 in vertex firstarc 1 A 0 B 0 C 0 D 0 E 1 F 0 3 0 0 5 2 3 3 5 ADF00AF拓扑排序拓扑排序012345 in vertex firstarc 0 A 0 B 0 C 0 D 0 E 0 F 0 3 0 0 5 2 3 3 5 AFAF1. 栈或队列栈或队列S初始化；累加器初始化；累加器count初始化；初始化；2. 扫描顶点表，将没有前驱的顶点压栈或入队；扫描顶点表，将没有前驱的顶点压栈或入队；3. 当栈或队列当栈或队列S非空时循环非空时循环 3.1 退出退出vj栈顶或队首元素；输出栈顶或队首元素；输出vj；累加器加；累加器加

13、1 3.2 将顶点将顶点vj的各个邻接点的入度减的各个邻接点的入度减1； 3.3 将新的入度为将新的入度为0的顶点入栈或入队；的顶点入栈或入队；4. if (countvertexNum) 输出有回路信息；输出有回路信息；拓扑排序算法拓扑排序算法伪代码伪代码作业作业: 请编程求请编程求AOV网的拓扑排序。网的拓扑排序。AOE网：在一个表示工程的带权有向图中，用顶点表示事网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称，称这样的有向图叫做边表示活动的网，简称A

14、OE网。网。AOE网中没有入边的顶点称为始点或源点），没有出边网中没有入边的顶点称为始点或源点），没有出边的顶点称为终点或汇点）。的顶点称为终点或汇点）。 AOE网的性质：网的性质： 只有在某顶点所代表的事件发生后，从该顶点出发的只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；各活动才能开始； 只有在进入某顶点的各活动都结束，该顶点所代表的只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。事件才能发生。abcdefghk64521187244例如例如: :整个工程完成的时间为：从有向图的始整个工程完成的时间为：从有向图的始点到终点的最长路径点到终点的最长路径始点终点61

15、74V3V3V1V1V4V4V6V6V5V5V2V2a4=3a4=3a1=3a1=3a2=2a2=2a6=3a6=3a5=4a5=4a3=2a3=2a7=2a7=2a8=1a8=1顶点表示事件顶点表示事件边表示活动边表示活动事件事件VjVj发生表示发生表示 akak已结束已结束ak VjVi事件事件ViVi发生表示发生表示 akak可以开始可以开始 AOE网可以回答下列问题：网可以回答下列问题： 1. 完成整个工程至少需要多少时间完成整个工程至少需要多少时间?2. 为缩短完成工程所需的时间为缩短完成工程所需的时间, 应当加快哪些活动应当加快哪些活动? 从始点到终点的路径可能不止一条，只有各条路

16、径上所有活从始点到终点的路径可能不止一条，只有各条路径上所有活动都完成了，整个工程才算完成。因而，完成整个工程所需动都完成了，整个工程才算完成。因而，完成整个工程所需的最短时间取决于从始点到终点的最长路径长度，即这条路的最短时间取决于从始点到终点的最长路径长度，即这条路径上所有活动的持续时间之和。这条路径长度最长的路径就径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径。叫做关键路径。事件事件Vj 的最早发生时间的最早发生时间Vej，是从源点到顶点，是从源点到顶点Vj的最大路径长的最大路径长度。度。事件事件Vj 的最迟发生时间的最迟发生时间Vlj， 指在不推迟整个工期的前提下，指

17、在不推迟整个工期的前提下，事件最晚必须发生的时间。事件最晚必须发生的时间。活动活动ak的最早开始时间的最早开始时间ek，该活动的尾事件的最早发生时间，该活动的尾事件的最早发生时间。活动活动ak的最晚开始时间的最晚开始时间lk，它的弧头顶点事件允许的最晚发生，它的弧头顶点事件允许的最晚发生时间减去该活动持续的时间。时间减去该活动持续的时间。活动活动ak 的时间余量的时间余量diffk =lk-ek时间余量为时间余量为0者即为关键活者即为关键活动动ak VjVivek是指从始点开始到顶点是指从始点开始到顶点vk的最大路径长度。这的最大路径长度。这个长度决定了所有从顶点个长度决定了所有从顶点vk发出

18、的活动能够开工的发出的活动能够开工的最早时间。最早时间。 ve1=0vek=maxvej+len (pk) pk表示所有到达表示所有到达vk的有向边的集合的有向边的集合 事件的最早发生时间事件的最早发生时间vek vjvkv2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4v2v7v6v5v4v1v3v9v8vek064577161418vek=maxvej+lenvlk是指在不推迟整个工期的前提下是指在不推迟整个工期的前提下,事件事件vk允许的允许的最晚发生时间。最晚发生时间。 事件的最迟发生时间事件的最迟发生时间v

19、lk vjvjvkvlk=minvlj-len（sk）sk为所有从为所有从vk发出的有向边的集合发出的有向边的集合v2v7v6v5v4v1v3v9v8vekvlk0645771614181814161078660v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4vlk=minvlj-len 活动的最早开始时间活动的最早开始时间ei 若活动若活动ai是由弧是由弧表示，则活动表示，则活动ai的最早开始的最早开始时间应等于事件时间应等于事件vk的最早发生时间。因而，有：的最早发生时间。因而，有： ei=vek v2v1v3

20、v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4v2v7v6v5v4v1v3v9v8vek064577161418a2a7a6a5a4a1a3a9a8ei000645777a10a111614ei=vek 活动活动ai的最晚开始时间是指，在不推迟整个工期的的最晚开始时间是指，在不推迟整个工期的前提下，前提下， ai必须开始的最晚时间。必须开始的最晚时间。若若ai由弧由弧表示，则表示，则ai的最晚开始时间要保证的最晚开始时间要保证事件事件vj的最迟发生时间不拖后。因而，有：的最迟发生时间不拖后。因而，有： li=vlj-len 活动的最晚开始时间活动的最晚开始时间liv2v7v6v5v4v1v3v9v8vlk1814161078660li10778663201614v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4a2a7a6a5a4a1a3a9a8a10a11v2v7v6v5v4v1v3v9v8vlk1814161078660li=vlj-len a2a7a6a5a4a1a3a9