数据结构第五5.pptx

第五章 图 5.1 基本概念 5.2 图的存储结构 5.3 图的遍历 5.4 拓扑排序 5.5 关键路径 5.6 最短路径 5.7 最小支撑树 5.8 图的应用;5.5.1 基本概念 边表示活动(Activity) 边的权值表示活动的持续时间(Duration) 顶点表示入边的活动已完成，出边的活动可以开始的状态，也称为事件(Event)这样的有向、无环、加权图被称做AOE (Activity On Edges)网 ;[例] 某工程 源点：表示整个工程的开始（入度为零）。 汇点：表示整个工程的结束（出度为零）。 完成整个工程至少需要多少时间？ 为缩短工程的时间，应当加快哪些活动？;从源点到各顶点的路径可能不止一条，路径长度也可能不同。只有各条路径上所有活动都完成了，整个工程才算完成。 因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度为最长的路径就叫做关键路径. 路径长度：指路径上的各有向边的权值之和。 关键活动：关键路径上的活动。;关键事件有关的量： 事件vj的最早发生时间ve(j):从源点v0到vj的最长路径长度。 事件vj的最迟发生时间vl(j):在保证汇点的最早发生时间不推迟的前提下，事件vj允许的最迟开始时间，等于ve(n?1)减去从vj到vn?1的最长路径长度。; ;● 关键活动有关的量： ③ 活动 ai 的最早开始时间 e(i): 设活动 ai 在有向边 vj ,vk 上，e(i) 是从源 点 v0 到 vj 的最长路径长度。因此 e(i)?ve(j) .; ● 关键活动有关的量： ④ 活动 ai 的最迟开始时间 l(i): 在不延误整个工程完成时间的前提下, 活动 ai 最迟的开始时间。设活动ai 在有向边vj ,vk上, 则 l(i)?vl(k)?weight(?j, k?); ;关键活动: 活动的最迟开始时间等于活动的最早开始时间，即l(i)＝e(i) .;求关键活动的算法 求关键活动的基本步骤： ①对AOE网进行拓扑排序, 按拓扑次序求出各顶点事件的最早发生时间ve, 若网中有回路, 则终止算法； ② 按拓扑序列的逆序求各顶点事件的最迟发生时间vl; ③根据ve和vl的值，求各活动的最早开始时间e(i)与最迟开始时间l(i)，若e(i)=l(i)，则 i 是关键活动。; [例] 求关键活动 –– 第1步; ; [例] 求关键活动–– 第2步; ;[例] 求关键活动–– 第3步：;算法CriticalPath () /* 图的关键路径算法 */ CPath1[计算事件的最早发生时间] FOR i = 1 TO n DO ve [i] ?0. FOR i = 1 TO n–1 DO /*（1）按顶点的拓扑序列计算各事件的最早发生时间*/ ( p?adjacent(Head [i]) . WHILE p DO ( k ? VerAdj (p) . IF (ve[i] + cost (p) ve[k] ) THEN ve[k] ?ve[i] + cost (p) . p?link(p)));CPath2[计算事件的最迟发生时间] FOR i = 1 TO n DO vl[i] ? ve[n] . FOR i = n–1 TO 1 STEP –1 DO /*（2）按拓扑逆序计算事件的最迟发生时间*/ ( p?adjacent (Head[i]) . WHILE p DO ( k?VerAdj(p) . IF (vl[k] – cost (p) vl[i] ) THEN vl[i] ?vl[k] – cost(p) . p?link(p)));CPath3[求诸活动的最早开始时间和最迟开始时间] FOR i = 1 TO n DO ( p?adjacent (Head [i]) . WHILE p DO ( k?VerAdj (p) . e?ve[i] . l?vl[k] – cost(p) . IF l = e THEN PRINT i, k is Critical Activity! p?link(p))) ?;时间复杂性： 对定点进行拓扑排序的时间复杂性为O(n+e), 以拓扑排序求ve[i]和以拓扑逆序求vl[i]时, 所需时间为均为O(e), 求各个活动的e[k]和l[k]的时间复杂度为O(e), 整个算法的时间复杂性是O(n+