图最小生成树-(精选·公开·课件).pptVIP

拓扑排序的过程 关键路径 如果在有向无环的带权有向图中 用有向边表示一个工程中的各项活动(Activity) 用边上的权值表示活动的持续时间(Duration) 用顶点表示事件(Event) 则这样的有向图叫做用边表示活动的网络，简称AOE (Activity On Edges)网络。 AOE网是一个带权的有向无环图。 AOE网络在某些工程估算方面非常有用。例如，可以使人们了解： (1) 完成整个工程至少需要多少时间(假设网络中没有环)? (2) 为缩短完成工程所需的时间, 应当加快哪些活动? 定义几个与计算关键活动有关的量： 事件Vi 的最早可能开始时间Ve(i) 是从源点V0 到顶点Vi 的最长路径长度。 事件Vi 的最迟允许开始时间Vl[i] 是在保证汇点Vn-1 在Ve[n-1] 时刻完成的前提下，事件Vi 的允许的最迟开始时间。 活动ak 的最早可能开始时间 e[k] 设活动ak 在边 Vi , Vj 上，则e[k]是从源点V0到顶点Vi 的最长路径长度。因此, e[k] = Ve[i]。 活动ak 的最迟允许开始时间 l[k] l[k]是在不会引起时间延误的前提下，该活动允许的最迟开始时间。 l[k] = Vl[j] - dur(i, j)。 其中，dur(i, j)是完成ak 所需的时间。 时间余量 l[k] - e[k] 表示活动ak 的最早可能开始时间和最迟允许开始时间的时间余量。l[k] == e[k]表示活动ak 是没有时间余量的关键活动。 为找出关键活动, 需要求各个活动的 e[k] 与 l[k]，以判别是否 l[k] == e[k]. 为求得e[k]与 l[k]，需要先求得从源点V0到各个顶点Vi 的 Ve[i] 和 Vl[i]。 从Ve[0] = 0开始，向前递推 Vj, Vi ? S2, i = 1, 2, ?, n-1 其中, S2是所有指向顶点Vi 的有向边 Vj , Vi 的集合。 从Vl[n-1] = Ve[n-1]开始，反向递推 Vi, Vj ? S1, i = n-2, n-3, ?, 0 其中, S1是所有从顶点Vi 发出的有向边 Vi , Vj 的集合。 这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。 设活动ak (k = 1, 2, …, e)在带权有向边 Vi , Vj 上, 它的持续时间用dur (Vi , Vj ) 表示，则有 e[k] = Ve[i]； l[k] = Vl[j] - dur(Vi , Vj )；k = 1, 2, …, e。这样就得到计算关键路径的算法。 计算关键路径时，可以一边进行拓扑排序一边计算各顶点的Ve[i]。为了简化算法，假定在求关键路径之前已经对各顶点实现了拓扑排序，并按拓扑有序的顺序对各顶点重新进行了编号。算法在求Ve[i], i=0, 1, …, n-1时按拓扑有序的顺序计算，在求Vl[i], i=n-1, n-2, …, 0时按逆拓扑有序的顺序计算。 【例7-3】请给出图7-24所示的有向图G的拓扑排序过程。 图7-24有向图G及其邻接矩阵 【解】依据拓扑排序算法，将图7-24中入度为0的两个顶点l和5相继入栈；顶点5出栈，输出，且以顶点5为尾的弧的另一顶点入度减一，如另一顶点2的入度值由2变为1，另一顶点6的入度值由1变为0。将入度为0的顶点6入栈；顶点6出栈，输出，且以顶点6为尾的弧的另一顶点入度减一，如另一顶点4的入度值由2变为1；依次类推得到拓扑序列：561234，拓扑排序过程栈的变化见图7-25。入度为0的顶点可以按不同顺序入栈，因此还可以得到其它拓扑序列：152364，152634，156234， 512364，516234，512634。 图7-25 拓扑排序过程的栈 在AOE网络中, 有些活动顺序进行，有些活动并行进行。 从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。 因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。 图7-26就是一个AOE网，该网中有11个活动和9个事件。每个事件表示在它之前