第16讲 拓扑排序与关键路径

1、第十六讲第十六讲 拓扑排序与关键路径拓扑排序与关键路径 主要内容2. 关键路径关键路径 AOV网：网：在一个表示工程的有向图中，用顶点表示在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有活动，用弧表示活动之间的优先关系，称这样的有向图为向图为顶点表示活动顶点表示活动的网，简称的网，简称AOV网。网。 什么是工程？工程有什么共性？什么是工程？工程有什么共性？AOV网中出现回路意味着什么？网中出现回路意味着什么？AOV网 AOV网：网：在一个表示工程的有向图中，用顶点表示在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有活动，用弧表示活

2、动之间的优先关系，称这样的有向图为向图为顶点表示活动顶点表示活动的网，简称的网，简称AOV网。网。 2.AOV网中不能出现回路网中不能出现回路 。AOV网特点：网特点：1.AOV网中的弧表示活动之间存在的某种制约关系。网中的弧表示活动之间存在的某种制约关系。什么是工程？工程有什么共性？什么是工程？工程有什么共性？AOV网 C1C2C3C4C6C5C7AOV网 拓扑序列：拓扑序列：设设G=(V，E)是一个具有是一个具有n个顶点的有向个顶点的有向图，图，V中的顶点序列中的顶点序列v1, v2, , vn称为一个拓扑序列，称为一个拓扑序列，当且仅当满足下列条件：若从顶点当且仅当满足下列条件：若从顶点

3、vi到到vj有一条路径有一条路径，则在顶点序列中顶点，则在顶点序列中顶点vi必在顶点必在顶点vj之前。之前。拓扑排序：拓扑排序：对一个有向图构造拓扑序列的过程称为对一个有向图构造拓扑序列的过程称为拓扑排序拓扑排序 。拓扑序列使得拓扑序列使得AOV网中所有应存在的前驱和后继网中所有应存在的前驱和后继关系都能得到满足。关系都能得到满足。拓扑排序 基本思想：基本思想： 从从AOV网中选择一个没有前驱的顶点并且输出；网中选择一个没有前驱的顶点并且输出； 从从AOV网中删去该顶点，并且删去所有以该顶点网中删去该顶点，并且删去所有以该顶点为尾的弧；为尾的弧； 重复上述两步，直到全部顶点都被输出，或重复上述

4、两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。网中不存在没有前驱的顶点。 拓扑排序的结果？拓扑排序的结果？拓扑排序 C1C2C3C4C6C5C7拓扑序列：拓扑序列： C1, C2, C3, C4, C5, C6, C7 拓扑排序 C1C2C3C4C6C5拓扑序列：拓扑序列： C1, C2, C3, 说明说明AOV网中网中存在回路。存在回路。 拓扑排序 设计数据结构设计数据结构 1. 图的存储结构：采用邻接表存储图的存储结构：采用邻接表存储 ，在顶点，在顶点表中增加一个入度域。表中增加一个入度域。 顶点表结点顶点表结点 in vertexfirstedge2. 栈栈S：存储所有无

5、前驱的顶点。：存储所有无前驱的顶点。拓扑排序 (a) 一个一个AOV网网 (b) AOV网的邻接表存储网的邻接表存储 012345 in vertex firstedge3 A 0 B1 C3 D0 E2 F 0 3 0 0 5 2 3 3 5 ABCDEF拓扑排序 012345 in vertex firstedge 3 A 0 B 1 C 3 D 0 E 2 F 0 3 0 0 5 2 3 3 5 ABCDEFBE拓扑排序 012345 in vertex firstedge 3 A 0 B 1 C 3 D 0 E 2 F 0 3 0 0 5 2 3 3 5 ABCDEFBE0C21拓扑排

6、序 012345 in vertex firstedge 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 firstedge 2 A 0 B 0 C 1 D 0 E 1 F 0 3 0 0 5 2 3 3 5 ABDFB D01拓扑排序 012345 in vertex firstedge 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 firstedge 0 A 0 B 0 C 0 D 0 E 0 F

7、0 3 0 0 5 2 3 3 5 AFAF拓扑排序 1. 栈栈S初始化；累加器初始化；累加器count初始化；初始化；2. 扫描顶点表，将没有前驱的顶点压栈；扫描顶点表，将没有前驱的顶点压栈；3. 当栈当栈S非空时循环非空时循环 3.1 vj=退出栈顶元素；输出退出栈顶元素；输出vj；累加器加；累加器加1； 3.2 将顶点将顶点vj的各个邻接点的入度减的各个邻接点的入度减1； 3.3 将新的入度为将新的入度为0的顶点入栈；的顶点入栈；4. if (countvertexNum) 输出有回路信息；输出有回路信息；拓扑排序算法拓扑排序算法伪代码伪代码拓扑排序 主要内容1. 拓扑排序拓扑排序 AO

8、E网：网：在一个表示工程的带权有向图中，用顶点表在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做持续时间，称这样的有向图叫做边表示活动边表示活动的网，简的网，简称称AOE网网。AOE网中没有入边的顶点称为网中没有入边的顶点称为始点始点（或源（或源点），没有出边的顶点称为点），没有出边的顶点称为终点终点（或汇点）。（或汇点）。 AOE网的性质：网的性质： 只有在某顶点所代表的事件发生后，从该顶点出只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；发的各活动才能开始； 只有在进

9、入某顶点的各活动都结束，该顶点所代只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。表的事件才能发生。AOE网 事件事件 事件含义事件含义 v1 开工开工 v2 活动活动a1完成，活动完成，活动a4可以开始可以开始 v3 活动活动a2完成，活动完成，活动a5可以开始可以开始 v9 活动活动a10 和和a11完成，整个工程完成完成，整个工程完成v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4AOE网 AOE网可以回答下列问题：网可以回答下列问题：1. 完成整个工程完成整个工程至少至少需要多少时间需要多少时间

10、?2. 为缩短完成工程所需的时间为缩短完成工程所需的时间, 应当加快哪些活动应当加快哪些活动? 从始点到终点的路径可能不止一条，只有各条路径上从始点到终点的路径可能不止一条，只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的最短时间取决于从始点到终点的整个工程所需的最短时间取决于从始点到终点的最长最长路径长度路径长度，即这条路径上所有活动的持续时间之和。，即这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做这条路径长度最长的路径就叫做关键路径关键路径。AOE网 关键路径：关键路径：在在AOE网中，从始点到终点具有

11、最大路径网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。径称为关键路径。关键活动：关键活动：关键路径上的活动称为关键活动。关键路径上的活动称为关键活动。 由于由于AOE网中的某些活动能够同时进行，故完成整网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为始点到终点的最大路个工程所必须花费的时间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期。径长度。关键路径长度是整个工程所需的最短工期。 关键路径 要找出关键路径，必须找出要找出关键路径，必须找出关键活动关键活动, 即不按

12、期完成即不按期完成就会影响整个工程完成的活动。就会影响整个工程完成的活动。首先计算以下与关键活动有关的量：首先计算以下与关键活动有关的量： 事件的最早发生时间事件的最早发生时间vek 事件的最迟发生时间事件的最迟发生时间vlk 活动的最早开始时间活动的最早开始时间ei 活动的最晚开始时间活动的最晚开始时间li最后计算各个活动的时间余量最后计算各个活动的时间余量 lk - ek，时间余量为，时间余量为0者即为关键活动。者即为关键活动。关键路径 vek是指从始点开始到顶点是指从始点开始到顶点vk的最大路径长度。这的最大路径长度。这个长度决定了所有从顶点个长度决定了所有从顶点vk发出的活动能够开工的

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

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

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