数据结构与算法12

1、数据结构与算法1Chapter 10图-22拓扑排序对于拓扑分类的研究，主要涉及的数据结构是无环路有向图。不存在有向环路的有向图简称为无环路有向图。1234无环路有向图1234有环路有向图3拓扑排序计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。4 C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数

2、据结构 C3, C2 C5 高级语言程序设计 C2 C6 编译方法 C5, C4 C7 操作系统 C4, C9 C8 普通物理 C1 C9 计算机原理 C8 C1C8C9C7C3C4C2C5C6学生课程学习工程图5拓扑排序和AOV网络可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边表示活动的关系。Vi 必须先于活动Vj 进行。这种有向图叫做顶点表示活动的AOV网络(Activity On Vertices)。 在AOV网络中，如果活动Vi必须在活动Vj之前进行，则存在有向边，AOV网络中不能出现有向回路，即有向环。在AOV网络中如果出现了有向环，则意味着某项活动应以自己作为先

3、决条件。因此，对给定的AOV网络，必须先判断它是否存在有向环。6拓扑排序和AOV网络检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点 (代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前导和后继关系都能得到满足。 这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑分类，也叫拓扑排序。如果通过拓扑分类能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。7给定一个无环路有向图G=(V,E) , 各结点的编号为v=

4、(1,2, ,n)。要求对每一个结点 i 重新进行编号，使得若 i 是 j 的前导，则有labelilabelj。即拓扑分类是将无环路有向图排成一个线性序列，使当从结点 i 到结点 j 存在一条边，则在线性序列中，将 i 排在 j 的前面。 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6C1C8C9C7C3C4C2C5C68输入AOV网络。令 n 为顶点个数。 在AOV网络中选一个入度为0的顶点, 并输出之; 从图中删去该顶点, 同时删去所有它发出的有向边; 重复以上

5、1、2 步, 直到全部顶点均已输出，拓扑有序序列形成，拓扑分类完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前导，再也找不到入度为0的顶点了。这时AOV网络中必定存在有向环。拓扑排序算法9拓扑分类的过程-1(a)无环有向图(b)输出顶点4(c)输出顶点0(d)输出顶点340310拓扑分类的过程-2(e)输出顶点2(f)输出顶点1(g)输出顶点0(h)拓扑分类完成403215 最后得到的拓扑有序序列为 4 , 0 , 3 , 2 , 1 , 5 。它满足图中给出的所有前导和后继关系，对于本来没有这种关系的顶点，如C0、C4和C2，也排出了先后次序关系。11

6、AOE网络（Activity On Edge）以顶点代表事件，有向边代表活动，有向边的权表示一向活动所需的时间。顶点所代表的事件是指它的入边代表的活动都以完成，由它的出边代表的活动可以开始这样的一种状态。AOE网络常常用来估算一项工程的完成时间。AOE网络只有一个开始顶点（入度为0）和一个结束顶点（出度为0）。关键路径和AOE网络v6源点起始点v0v3v2v1v4v5v8a0=6a5=2a2=5a1=4a4=1a3=1a6=9a7=8a8=4a10=4a9=2汇点结束点AOE网v712只有在某个顶点所代表的事件发生后，从该顶点出发的各有向边代表的活动才能开始;只有在进入某一顶点的各有向边代表的

7、活动已经结束，该顶点所代表的事件才能发生；表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度为0的开始顶点（源点）和唯一的出度为0的结束点（汇点）。AOE网的性质v6源点起始点v0v3v2v1v4v5v8a0=6a5=2a2=5a1=4a4=1a3=1a6=9a7=8a8=4a10=4a9=2汇点结束点AOE网v713AOE网研究的主要问题 如果用AOE 网表示一项工程，那么仅仅考虑各个子工程之间的优先关系还不够，更多地是关心整个工程完成的最短时间是多少，哪些活动的延迟将影响整个工程进度,而加速这些活动能否提高整个工程的效率,因此AOE网有待研究的问题是:(1) 完成整个工程至少需要多

8、少时间？(2) 哪些活动是影响工程进度的关键活动？v6源点起始点v0v3v2v1v4v5v8a0=6a5=2a2=5a1=4a4=1a3=1a6=9a7=8a8=4a10=4a9=2汇点结束点AOE网v714路径长度、关键路径、关键活动路径长度：是指从源点到汇点路径上所有活动的持续时间之和。关键路径：在AOE网中，由于有些活动可以并行，所以完成工程的最短时间是从源点到汇点的最大路径长度。因此，把从源点到汇点具有最大长度的路径称为关键路径。一个AOE中，关键路径可能不只一条。关键活动：关键路径上的活动称为关键活动。v6源点起始点v0v3v2v1v4v5v8a0=6a5=2a2=5a1=4a4=1

9、a3=1a6=9a7=8a8=4a10=4a9=2汇点结束点AOE网v715 事件Vj 的最早可能发生时间VE(j) 是从源点V1 到顶点Vj 的最长路径长度。活动ai 的最早可能开始时间 E(k) 设活动ai 在边上, 则E(i)也是从源点V1到顶点Vj 的最长路径长度。这是因为事件Vj发生表明以Vj为起点的所有活动ai可以立即开始。因此, E(i) = VE(j) .( 1 ) 关键路径和关键活动性质分析：（与计算关键活动有关的量）v6源点起始点v0v3v2v1v4v5v8a0=6a5=2a2=5a1=4a4=1a3=1a6=9a7=8a8=4a10=4a9=2汇点结束点AOE网v716事

10、件Vk的最迟发生时间VL(k) 是在保证汇点Vn在VE(n)时刻完成的前提下，事件Vk的允许的最迟开始时间。 在不推迟工期的情况下，一个事件 最迟发生时间VL(k)应该等于汇点的最早发生时间VE(n )减去从Vk到Vn的最大路径长度。v6源点起始点v0v3v2v1v4v5v8a0=6a5=2a2=5a1=4a4=1a3=1a6=9a7=8a8=4a10=4a9=2汇点结束点AOE网v717 活动ai 的最迟允许开始时间 L(i) 是指在不会引起工期延误的前提下，活动ai允许的最迟开始时间。 因为事件Vk发生表明以Vk为终点的入边所表示的所有活动均已完成，所以事件Vk的最迟发生时间VL(k)也是

11、所有以Vk为终点的入边所表示的活动ai可以最迟完成时间。 显然，为不推迟工期，活动ai的最迟开始时间L(i)应该是ai的最迟完成时间VL(k)减去ai的持续时间，即 L(i) = VL(k) - ACTjk .( 2 ) 其中, ACTjk是活动ai 的持续时间（ 上的权）。VjVkai18时间余量 L(i) - E(i) L(i) - E(i)表示活动 ak 的最早可能开始时间和最迟允许开始时间的时间余量。 关键路径上的活动都满足：L(i) = E(i) .( 3 ) L(i) = E(i)表示活动是没有时间余量的关键活动。 由上述分析知，为找出关键活动，需要求各个活动的E(i)与 L(i)

12、，以判别一个活动ai是否 满足L(i) = E(i)。 E(i)和L(i)可有公式 (1)和(2)。而VE(k) 和VL(k)可由拓扑分类算法得到。 利用拓扑分类算法求关键路径和关键活动。19Step1(前进阶段)：从源点V1出发，令VE(1) = 0，按拓扑序列次序求出其余各顶点事件的最早发生时间: 利用拓扑分类算法求关键路径和关键活动 其中T是以顶点Vk为尾的所有边的头顶点的集合(2kn)如果网中有回路，不能求出关键路径则算法中止；否则转Step2。其中S是以顶点Vj为头的所有边的尾顶点的集合(2jn-1)jTVE(k) = max VE(j)+ACTjk Step2(回退阶段)：从汇点V

13、n出发，令VL(n) = VE(n)，按逆拓 扑有序求其余各顶点的最晚发生时间：kSVL(j) = min VL(k)+ACTjk 20Step3： 求每一项活动ai的最早开始时间: E( i ) = VE( j ) 最晚开始时间: L( i ) = VL( k ) - ACTjk 若某条边满足E( i ) = L( i )，则它是关键活动。为了简化算法, 可以在求关键路径之前已经对各顶点实现拓扑排序, 并按拓扑有序的顺序对各顶点重新进行了编号。不是任意一个关键活动的加速一定能使整个工程提前。想使整个工程提前，要考虑各个关键路径上所有关键活动。21例1:活动e(i)l(i)l(i)-e(i)a

14、0a1a2a3a4a5a6a7a8a9a1000002204466046259478177071141617215150注：Ve(i)：事件最早可能发生时间 源点到达该事件的最长路经Vl(i)：事件最迟发生时间 VE(n) - maxLik e(i)：活动最早可能开始时间 Ve( 活动起点 ) l(i)：活动最迟允许开始时间 Vl( 活动终点 ) - ai 事件vevlv0v1v2v3v4v5v6v7v80066465977711161715151919v6源点起始点v0v3v2v1v4v5v8a0=6a5=2a2=5a1=4a4=1a3=1a6=9a7=8a8=4a10=4a9=2汇点结束点

15、AOE网v722123654a1=3a2=2a4=3a3=2a5=4a6=1a7=2a8=3例2:顶点Ve(i)Vl(i)活动e(i)l(i)l(i)-e(i)123456a1a2a3a4a5a6a7a8032668042678003326621044276510110103注：事件最早可能发生时间Ve(i) 源点到达该事件的最长路经事件最迟发生时间Vl(i) VE(n)-maxLik活动最早可能开始时间 e(i) Ve(活动起点)活动最迟允许开始时间 l(i) Vl(活动终点)-ai 23单源最短路径D1 D2 D3 D4 D5 10 30 100D 10 30 100 50 20 10 2

16、0 60 C集合 S = 1 1, 2, 3, 4, 5 20124351010030105060V0Dijkstra算法基本思想：集合S的 初值为S=1D为各顶点当前最小路径从V-S中选择顶点w，使Dw的值最小 并将 w加入集合 S，则w的最短路径已 求出。调整其他各结点的当前最小路径 Dk=minDk, Dw+Cwk直到S中包含所有顶点2412435101003010502060V0循环 S w D2 D3 D4 D5初态 1 - 10 30 100 1 1,2 2 10 60 30 100 2 1,2,4 4 10 50 30 90 3 1,2,4,3 3 10 50 30 60 4 1

17、,2,4,3,55 10 50 30 60算法的逐步求精过程：算法：Void Dijkstra( G ) S = 1 ; for( i=2; i=n; i+ ) Di = C1i; for( i=1; in; i+ ) 从V-S中选出一个顶点w,使Dw最小； S = S + w ; for ( V-S中的每一个顶点v ) Dv=min( Dv, Dw+Cwv ); 25循环 S w D1 D2 D3 D4 D5初态 0 - 10 30 100 1 0,2 2 10 60 30 100 2 0,2,4 4 10 50 30 90 3 0,2,4,3 3 10 50 30 60 4 0,2,4,3

18、,5 5 10 50 30 60 5 0,2,4,3,5,1 1 10 50 30 6050324100601030105020V015D0 D1 D2 D3 D4 D5 10 30 100D 10 30 100 5 50 10 20 60 C例题26每一对顶点间的最短路径基本思想： 假设求顶点vi到顶点vj的最短路径。如果从 vi 到 vj 存在一条长度为Cij的路径，该路径不一定是最短路径，尚需进行 n 次试探。首先考虑路径 (vi,v0,vj) 是否存在。如果存在，则比较 (vi,vj) 和 (vi,v0,vj) 的路径长度取长度较短者为从vi到vj的中间顶点的序号不大于0的最短路径。假

19、设在路径上再增加一个顶点v1,也就是说，如果 (vi,vj)和 (v1,vj) 分别是当前找到的中间顶点的序号不大于0的最短路径,那么 (vi,v1,vj)就是有可能是从vi到vj的中间顶点的序号不大于1的最短路径。 将它和已经得到的从vi到vj中间顶点序号不大于0的最短路径相比较，从中选出中间顶点的序号不大于1的最短路径，在增加一个顶点v2, 继续进行试探。 一般情况下，若 (vi,vk) 和 (vk,vj) 分别是从 vi到vk和从vk到Vj的中间顶点序号不大于 k-1 的最短路径，则将 (vi,vk,vj) 和已经得到的从 vi到 vj且中间顶点序号不大于k-1的最短路径相比较，其长度较短者便是从vi到 vj 的中间顶点的序号不大于