数据结构课件第7章图1章节幻灯片.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 若 i , j 是网中有向边，则 i 是 j 的直接前驱； j 是 i 的直接后继。 AOV 网中不允许有回路，因为如 果有回路存在，则表明某项活动以 自己为先决条件，显然这是荒谬的。 问题：如何判别 AOV 网中是否存在回路？ C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 AOV 网的特点： 若从 i 到 j 有一条有向路径，则 i 是 j 的前驱；j 是 i 的后继。 拓扑排序： 检测 AOV 网中是否存在环方法： 对有向图构造其顶 点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序 列中，则该 AOV 网必定不存在环。 在 AOV 网没有回路的前提下，我们将全部 活动排列成一个线性序列，使得若 AOV 网中有 弧 i, j 存在，则在这个序列中， i 一定排在 j 的前面，具有这种性质的线性序列称为拓扑有序 序列，相应的拓扑有序排序的算法称为拓扑排序。 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓扑排序的方法： 在有向图中选一个没有前驱的顶点且输出之。 从图中删除该顶点和所有以它为尾的弧。 重复上述两步，直至全部顶点均已输出；或者当图中 不存在无前驱的顶点为止。 C9, C10, C11, C6, C1, C12, C4, C2, C3, C5, C7, C8 拓扑序列： C1, C2, C3, C4, C5, C7, C9, C10, C11, C6, C12, C8 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 一个AOV网的拓扑序列不是唯一的 例：设一个工程有 11 项活 动， 9 个事件。 事件 v1 — 表示整个工程 开始（源点） 事件 v9 — 表示整个工程 结束（汇点） 7.5.2 关键路径 把工程计划表示为有向图，用顶点表示事件，弧表示 活动，弧的权表示活动持续时间。每个事件表示在它之前 的活动已经完成，在它之后的活动可以开始。称这种有向 图为边表示活动的网，简称为 AOE (Activity On Edge) 网。 a8=7 a9=4 a10=2 a11=4 a7=9 a4=1 a5=1 a6=2 a2=4 a1=6 v9 v8 v7 v6 v4 v5 v3 v2 v1 a3=5 对AOE网，我们关心两个问题： (1) 完成整项工程至少需要 多少时间？ (2) 哪些活动是影响工程进 度的关键？ a8=7 a9=4 a10=2 a11=4 a7=9 a4=1 a5=1 a6=2 a2=4 a1=6 v9 v8 v7 v6 v4 v5 v3 v2 v1 a3=5 路径长度 — 路径上各活动持续时间之和。 关键路径 — 路径长度最长的路径。 ve(j) — 表示事件 vj 的最早发生时间。 vl(j) — 表示事件 vj 的最迟发生时间。 e(i) — 表示活动 ai 的最早开始时间。 l(i) — 表示活动 ai 的最迟开始时间。 l(i) - e(i) — 表示完成活动 ai 的时间余量。 关键活动 — 关键路径上的活动，即 l(i) = e(i) 的活动。 ve(3) = 4 vl(3) = 6 e(5) = 4 l(5) = 6 l(5) - e(5) = 2 如何找 l(i) = e(i) 的关键活动？ 设活动 ai 用弧 j, k 表示，其持续时间记为：dut(j, k) 则有： (1) e(i) = ve(j) (2) l(i) = vl(k) - dut(j, k) j k ai (1) 从 ve(1) = 0 开始向前递推 (2) 从 vl(n) = ve(n) 开始向后递推 如何求 ve(j) 和 vl(j) ？ a8=7