20拓扑排序和关键路径

AOV网 -拓 扑 排 序有 向 无 环 图 及 其 应 用AOE网 -关 键 路 径有 向 无 环 图小 结 和 作 业有 向 无 环 图 的 应 用公 用 表 达 式 有 向 无 环 图一 、 定 义 ：一 个 无 环 的 有 向 图 ， 称 为 有 向 无 环 图 （ DAG图 ）V1V2V4 V5 V3 V7V6V8 V1V2V4 V5 V3V7V6V8DAG图 有 环 的 有 向 图DAG = Directed Acyclic Graph 有 向 无 环 图二 、 如 何 判 断 一 个 图 是 否 是 DAG？V1V2V4 V5 V3 V7V6V8 DAG图 V1V2V4 V5 V3 V7V6V8非 DAG图 有 向 无 环 图二 、 如 何 判 断 一 个 图 是 否 是 DAG？深 度 优 先 搜 索 没 有 出 现 指 向 祖 先 的 回 边 ， 即 ：没 有 一 个 顶 点 有 一 条 边 ， 指 向 遍 历 过 程 中 先访 问 过 的 顶 点 （ 并 且 这 些 顶 点 的 DFS函 数 没有 执 行 完 ） 有 向 无 环 图bool DAG(Graph G) for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访 问 标 志 数 组 初 始 化 InitStack(S);/存 放 顶 点 for (v=0; v=0; w=NextAdjVex(G,v,w) if (w in S) then return(FALSE);/有 回 边 if(!visitedw) if(!DFS-DAG(G, w) return(FALSE); Pop(S, v);/v的 所 有 邻 接 点 已 经 遍 历 完 return(TRUE); / DFS-T 公 用 表 达 式用 树 表 示 表 达 式 ：(a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e)* * + + ccc ddd eebba 公 用 表 达 式多 次 出 现 的 变 量 和 表 达 式 通 过 共 用 ， 减 少出 现 次 数 * * + + ccc ddd eebba * * + +c deba 拓 扑 排 序一 、 定 义由 集 合 上 的 一 个 偏 序 关 系 得 到 集 合 的 全 序 关 系 的操 作偏 序 ： 自 反 的 、 反 对 称 的 、 传 递 的全 序 ： R是 集 合 X上 的 偏 序 ， 对 于 集 合 X中 的 任 何元 素 x,y， 如 果 都 有 xRy或 者 yRx,则 称 R是 全 序 关系 拓 扑 排 序B DA C B DA C偏 序 就 是 集 合 中 的 部 分 成 员 可 以 比 较 。全 序 是 集 合 中 的 任 何 成 员 之 间 都 可 以 比 较 。偏 序 全 序 拓 扑 排 序 按 照 有 向 图 给 出 的 次 序 关 系 ， 将 图 中 顶 点 排 成一 个 线 性 序 列 ， 对 于 有 向 图 中 没 有 限 定 次 序 关 系的 顶 点 ， 则 可 以 人 为 加 上 任 意 的 次 序 关 系 。 由 此 所 得 顶 点 的 线 性 序 列 称 之 为 拓 扑 有 序 序列 拓 扑 排 序用 顶 点 表 示 活 动 ， 弧 表 示 活 动 间 的 优 先 关 系 的有 向 图 。AOV网 （ Activity On Vertex NetWork）AOV网 中 不 应 该 出 现 有 向 环 ： 如 果 存 在 环 ， 则 某项 活 动 以 自 己 为 先 决 条 件 ， 拓 扑 排 序B DA C可 求 得 拓 扑 有 序 序 列 ： A B C D 或 A C B D B DA C不 能 求 得 它 的 拓 扑 有 序 序 列 。因 为 图 中 存 在 一 个 回 路 B, C, D 拓 扑 排 序 拓 扑 排 序 -方 法 11、 从 有 向 图 中 选 取 一 个 没 有 前 驱 的 顶 点 ， 并输 出 之 ;2、 从 有 向 图 中 删 去 此 顶 点 以 及 所 有 以 它 为 尾的 弧 ;3、 重 复 上 述 两 步 ， 直 至 图 空 ， 或 者 图 不 空 但找 不 到 无 前 驱 的 顶 点 为 止 。 拓 扑 排 序 -方 法 1a cgb dh f eb h a c d g f e拓 扑 序 列 ： 在 算 法 中 需 要 用 定 量 的 描 述 替 代 定 性 的 概 念没 有 前 驱 的 顶 点 入 度 为 零 的 顶 点删 除 顶 点 及 以 它 为 尾 的 弧 弧 头 顶 点 的 入 度 减 1 拓 扑 排 序 -方 法 1 Status ToplogicalSort(ALGragh G)FindInDegree(G, indegree);InitStack(S);for(i=0;iG.vexnum;i+)if(!indegreei) push(S,i);count=0; /对 输 出 顶 点 计 数while (!EmptyStack(S) /whileif (countG.vexnum) return ERROR;else return OK; 拓 扑 排 序 -算 法 Status ToplogicalSort(ALGragh G)while (!EmptyStack(S) Pop(S, v); +count; printf(v); for (w=FirstAdj(v); w; w=NextAdj(G,v,w) -indegree(w); / 弧 头 顶 点 的 入 度 减 1 if (!indegreew) Push(S, w); /for/while 拓 扑 排 序 -算 法 总 的 时 间 复 杂 度 ： O(n+e)算 法 分 析 ： 拓 扑 排 序 -算 法 拓 扑 排 序 -方 法 2a cgb dh f eb h a c d g f e拓 扑 序 列 ： 对 有 向 无 环 图 利 用 深 度 优 先 搜 索 进 行 拓 扑 排 序 。 拓 扑 排 序 -方 法 2a cgb dh f eb h a c d g f e 此 图 的 一 个 拓 扑 序 列 为 ：退 出 DFS函 数 顺 序 ： e f g d c a h b 拓 扑 排 序 -方 法 2最 先 退 出 DFS函 数 的 顶 点 是 出 度 为 零 的 顶 点 ， 为 拓扑 排 序 序 列 中 最 后 一 个 顶 点 。因 此 ， 按 退 出 DFS函 数 的 先 后 记 录 下 来 的 顶 点 序 列即 为 逆 向 的 拓 扑 排 序 序 列 。结 论 ： 拓 扑 排 序 -方 法 2void DFS-ToplogicalSort (Graph G, int v) /如 何 确 定 v for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访 问 标 志 数 组 初 始 化 InitStack(S);/存 放 顶 点 ， 按 照 出 DFS的 次 序 for (v=0; v=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS-T(G, w); / 对 v的 尚 未 访 问 的 邻 接 顶 点 w递 归 调 用 DFS-T Push(S, v);/顶 点 v的 DFS函 数 执 行 完 毕 / DFS-T 拓 扑 排 序 -练 习a cgb dh f e写 出 下 图 的 所 有 的 拓 扑 序 列 关 键 路 径源 点 汇 点事 件 活 动 及 其 持 续 的 时 间AOE-网 (Activity on Edge):边 表 示 活 动 网 。a1=6a2=4 v8v1 V2V3v 4 v5 v6 v7 v9a3=5 a4=1a5=1a6=2 a7=9a8=7a9=4 a10=2a11=4 假 设 以 AOE网 表 示 一 个 施 工 流 图 ， 弧 上 的 权 值 表 示完 成 该 项 子 工 程 所 需 的 时 间 。1、 完 成 整 个 工 程 至 少 需 要 多 少 时 间 ？2、 哪 些 活 动 是 影 响 工 程 进 度 的 关 键 ？关 键 路 径AOE-网 是 一 个 带 权 的 有 向 无 环 图 ， 可 用 来 估 算工 程 的 完 成 时 间 。 路 径 最 长 的 路 径 叫 做 关 键 路 径影 响 工 程 进 度 的 活 动 叫 关 键 活 动关 键 路 径 上 的 活 动 一 定 是 关 键 活 动关 键 路 径 如 何 求 关 键 路 径用 e(i)和 l(i)分 别 表 示 活 动 ai的 最 早 开 始 时间 和 最 迟 开 始 时 间e(i)-l(i)为 活 动 ai 的 时 间 余 量e(i)=l(i)的 活 动 是 关 键 活 动 如 何 求 关 键 路 径ve(i)： 表 示 事 件 i的 最 早 开 始 时 间vl(i)： 表 示 事 件 i的 最 迟 开 始 时 间已 知 ve(1)=0， 计 算 其 余 顶 点 的 ve值 要 按 照顶 点 拓 扑 排 序 后 的 次 序 进 行ve(j)=max(ve(i) + dut() T,T是 以 j为 头 的 弧 的 集 合a1=6a2=4 v8v1 V2V3 v5 v7 v9a4=1a5=1 a7=9a8=7 a10=2a11=4V i到 Vj的 最 长 路 径 如 何 求 关 键 路 径vl(n-1)=ve(n-1)， 然 后 按 照 顶 点 逆 拓 扑 排序 后 的 次 序 求 其 余 顶 点 的 vlvl(i)=min(vl(j) - dut() S,S是 以 i为 尾 的 弧 的 集 合a1=6a2=4 v8v1 V2V3 v5 v7 v9a4=1a5=1 a7=9a8=7 a10=2a11=4 如 何 求 关 键 路 径用 e(i)和 l(i)分 别 表 示 活 动 ai的 最 早 开 始 间和 最 迟 开 始 时 间显 然 有 ：e(i)=ve(j)l(i)=vl(k)-dut(j,k) j kai 如 何 求 关 键 路 径a1=6a2=4 v8v1 V2V3v4 v5 v6 v7 v9a3=5 a4=1a5=1a6=2 a7=8a8=7a9=4 a10=2a11=4v1 v2 v3 v4 v5 v6 v7 v8 v9vevl 0 0 0 0 0 0 0 0 06 4 5 14 187 7 1518 18 18 18 18 18 18 18 186 476 6 080拓 扑 有 序 序 列 : v1 v2 v3 v4 v6 v5 v8 v7 v9逆 拓 扑 有 序 序 列 :v9 v7 v8 v5 v2 v3 v6 v4 v1 如 何 求 关 键 路 径a1 a2 a3el a4 a5 a6 a7 a8 a9 a10 a116 4 5 1 1 2 8 7 4 2 40 0 0 6 4 5 7 7 7 15 140 2 3 6 6 8 8 7 10 16 14a1=6a2=4 v8v1 V2V3v4 v5 v6 v7 v9a3=5 a4=1a5=1a6=2 a7=8a8=7a9=4 a10=2a11=40, 0 6, 64, 65, 8 7, 77, 10 15, 1614, 14 18, 18 如 何 求 关 键 路 径a1=6a2=4 v8v1 V2V3v 4 v5 v6 v7 v9a3=5 a4=1a5=1a6=2 a7=8a8=7a9=4 a10=2a11=4最 终 求 得 的 关 键 路 径 如 下 所 示 ： 关 键 路 径 算 法1） 输 入 n个 顶 点 和 e条 弧 ， 建 立 AOE网 存 储 结 构2） 求 出 网 G的 拓 扑 排 序令 ve0=0,求 其 余 结 点 的 最 早 发 生 时 间 ve(j)=max(ve(i) + dut() T,T是 以 j为 头 的 弧 的 集 合若 得 到 拓 扑 排 序 中 顶 点 个 数 n， 说 明 G中 存 在环 ， 算 法 终 止 。 关 键 路 径 算 法3） 求 出 G的 逆 向 拓 扑 序 列从 汇 点 出 发 ， 令 vl(n-1)=ve(n-1)求 其 余 各 顶 点 的 最 迟 发 生 时 间 ： vl(i)=min(vl(j) - dut() S,S是 以 i为 尾 的 弧 的 集 合 关 键 路 径 算 法4） 根 据 2） 和 3） 中 所 得 的 ve和 vl， 求 每 条 弧 上 的活 动 ai的 最 早 发 生 时 间 e(i)和 l(i)e(i)=ve(j)l(i)=vl(k)-dut(j,k) j kai5） 如 果 某 条 弧 上 的 活 动 ai满 足 e(i)=l(i)， 则 ai为 关键 活 动 。 如 何 求 关 键 路 径A练 习 ： 求 下 图 各 活 动 弧 ai的 e(ai)和 l(ai)， 个 事 件 vj的ve(vj)和 vl(vj)， 列 出 各 关 键 路 径 。BCD EF GH WX 1634 275106 11 17 129 1382116 关 键 路 径 算 法算 法 描 述 ：1） 有 向 网 AOE采 用 邻 接 表 作 为 存 储 结 构2） 栈 T： 拓 扑 序 列 顶 点 栈3） 栈 S： 0入 度 顶 点 栈4） 返 回 值 ：ERROR： 图 G中 有 回 路OK： 栈 T返 回 图 G的 一 个 拓 扑 有 序 序 列 关 键 路 径 算 法Status ToplogicalOrder( ALGragh G, Stack InitStack(S);for(i=0;iG.vexnum;i+)if(!indegreei) push(S,i); Initstack(T); count=0; ve0.G.vexnum-1=0;while (!EmptyStack(S) /whileif (countnextarc) k=p-adjvex; if(-indegree(k)=) Push(S,k); /入 度 -1为 0， 则 入 栈 if(vej+*(p-info)vek)vek= vej+*(p-info) /for /whileif (countnextarc)k=p-adjvex; dut=*(p-info);if(vlk-dutvlj)vlj=vlk-dut; /end of for/end of while/end of CriticalPath 关 键 路 径 算 法Status CriticalPath( ALGragh G)/输 出 G的 关 键 活 动for(j=0;jnextarc) k=p-adjvex; dut=*(p-info); ee=vej;el=vlk-dut; tag=(ee=el)?*:; printf(j,k,dut,ee,el,tag); /end of for(p)/end of status 关 键 路 径 算 法Status CriticalPath( ALGragh G)/输 出 G的 关 键 活 动for(j=0;jnextarc) k=p-adjvex; dut=*(p-info); ee=vej;el=vlk-dut; tag=(ee=el)?*:; printf(j,k,dut,ee,el,tag); /end of for(p)/end of status 关 键 路 径 算 法 分 析1.求 关 键 路 径 的 总 的 时 间 复 杂 度 ： O(n+e)2.AOE-网 求 出 的 路 径 可 能 大 于 一 条 。 这 种 情 况 下 只 有 同 时 提 高 所 有 关 键 路 径 上 的活 动 的 速 度 ， 才 能 使 整 个 工 期 缩 短 。 小 结 和 作 业1.拓 扑 排 序2.关 键 活 动 本 节 主 要 内 容 ： 1.什 么 是 拓 扑 排 序3. 拓 扑 排 序 算 法 1.什 么 是 关 键 活 动3.关 键 活 动 算 法 2.如 何 求 关 键 活 动 2.如 何 进 行 拓 扑 排 序 小 结 和 作 业思 考 题 ：下 列 关 于 AOE网 的 叙 述 中 ， 不 正 确 的 是 （ ） 。A 关 键 活 动 不 按 期 完 成 就 会 影 响 整 个 工 程 的 完 成 时 间B 任 何 一 个 关 键 活 动 提 前 完 成 ， 那 么 整 个 工 程 将 会 提 前 完 成C 所 有 的 关 键 活 动 提 前 完 成 ， 那 么 整 个 工 程 将 会 提 前完 成D 某 些 关 键 活 动 提 前 完 成 ， 那 么 整 个 工 程 将 会 提 前 完成作 业 ： 7.9， 7.10