数据结构(牛小飞)3拓扑排序

拓 扑 排 序拓 扑 排 序复 习小 结 和 作 业 复 习图 的 深 度 优 先 搜 索 ： 简 单 路 径图 的 广 度 优 先 搜 索 ： 最 短 路 径图 的 遍 历 方 法 v1v 3 v2 v5v6 v7v4 拓 扑 排 序问 题 的 引 入拓 扑 排 序 的 定 义拓 扑 排 序 方 法 1拓 扑 排 序 方 法 2练 习 拓 扑 排 序 -问 题 引 入某 学 校 的 部 分 课 程 结 构java语 言 数 据 结 构数 据 库 原 理 算 法 分 析 与 设 计操 作 系 统 软 件 工 程软 件 测 试如 何 制 定 教 学 计 划 ？ 拓 扑 排 序 -定 义按 照 有 向 图 给 出 的 次 序 关 系 ， 将 图 中 顶 点 排 成 一个 线 性 序 列 ， 对 于 有 向 图 中 没 有 限 定 次 序 关 系 的顶 点 ， 则 可 以 人 为 加 上 任 意 的 次 序 关 系 。由 此 所 得 顶 点 的 线 性 序 列 称 之 为 拓 扑 有 序 序 列 。 拓 扑 排 序 是 对 有 向 无 圈 图 的 顶 点 的 一 种 排 序 ， 使得 如 果 存 在 一 条 从 vi到 vj的 路 径 ， 那 么 在 排 序 中 vj就 出 现 在 vi的 后 面 。 显 然 ， 如 果 图 中 含 有 圈 ， 那 么 拓 扑 排 序 是 不 可 能 的 ，因 为 对 于 圈 上 的 两 个 顶 点 v和 w， v优 先 于 w同 时 w又 优先 于 v。 拓 扑 排 序 -定 义 B DA C不 能 求 得 它 的 拓 扑 有 序 序 列 。因 为 图 中 存 在 一 个 回 路 B, C, D拓 扑 排 序 -举 例 B DA C可 求 得 拓 扑 有 序 序 列 ： A B C D 或 A C B D拓 扑 排 序 -举 例 拓 扑 序 列 不 是 唯 一 的 。 v1v3 v2 v5v6 v7v4可 能 的 拓 扑 序 列 为 ： v1,v2,v5,v4,v3,v7,v6v1,v2,v5,v4,v7,v3,v6拓 扑 排 序 -举 例 拓 扑 排 序 -方 法 11、 从 有 向 图 中 选 取 一 个 没 有 前 驱 的 顶 点 ， 并 输 出 ;2、 从 有 向 图 中 删 去 此 顶 点 以 及 所 有 以 它 为 尾 的 弧 ;3、 重 复 上 述 两 步 ， 直 至 图 空 ， 或 者 图 不 空 但 找 不 到无 前 驱 的 顶 点 为 止 。 a cgb dh f eb h a c d g f e拓 扑 序 列 ： 拓 扑 排 序 -方 法 1 拓 扑 排 序 -方 法 11、 从 有 向 图 中 选 取 一 个 没 有 前 驱 的 顶 点 ， 并 输 出 ;2、 从 有 向 图 中 删 去 此 顶 点 以 及 所 有 以 它 为 尾 的 弧 ;3、 重 复 上 述 两 步 ， 直 至 图 空 ， 或 者 图 不 空 但 找 不 到无 前 驱 的 顶 点 为 止 。入 度 为 0的 顶 点 弧 头 顶 点 的 入 度 减 1 void topsort( ) for(int counter=0;counterNUM_VERTICES;counter+) Vertex v=findNewVertexOfIndegreeZero( ); /寻 找 一 个 尚 未 被 分 配 拓 扑 编 号 的 入 度 为 0的 顶 点if(v=null) /图 中 有 圈 throw new CycleFoundException(); v.topNum=counter; /顶 点 v的 拓 扑 编 号for each Vertex w adjacent to v w.indegree-; /弧 头 顶 点 的 入 度 减 1 拓 扑 排 序 -方 法 1 v1v3 v2 v5v6 v7v4 出 队 前 的 入 度顶 点 1 2 3 4 5 6 7 v1 v2 v3 v4 v5 v 6 v7入 队出 队 0123132v1 012132v2 10321v5 0131v4 200v3,v7v3 v710 0v6v1 v2 v5 v4p274, 9.2队 列 和 栈 是 否 都 能实 现 拓 扑 排 序 ？ ？ 拓 扑 排 序 -方 法 1 void topsort( ) throws CycleFoundException Queue q=new Queue( ); int counter=0; /对 输 出 顶 点 计 数 for each Vertex v if(v.indegree=0) /顶 点 的 入 度 为 0， 则 入 队 q.enqueue(v); while (!q.isEmpty( ) /如 果 队 列 非 空 if (counter!=NUM_VERTICES) /有 圈 throw new CycleFoundException( ); 拓 扑 排 序 -方 法 1 void topsort( ) throws CycleFoundException . while (!q.isEmpty( ) /如 果 队 列 非 空 . Vertex v=q.dequeue( );v.topNum=+counter;for each Vertex w adjacent to vif(-w.indegree=0)q.enqueue(w); 拓 扑 排 序 -方 法 1 总 的 时 间 复 杂 度 ： O(n+e)算 法 分 析 ： 拓 扑 排 序 -方 法 1 a cgb dh f eb h a c d g f e拓 扑 序 列 ： 拓 扑 排 序 -方 法 2 对 有 向 无 环 图 利 用 深 度 优 先 搜 索 进 行 拓 扑 排 序 。a cgb dh f eb h a c d g f e 此 图 的 一 个 拓 扑 序 列 为 ：退 出 DFS函 数 顺 序 ： e f g d c a h b 拓 扑 排 序 -方 法 2 最 先 退 出 DFS函 数 的 顶 点 是 出 度 为 零 的 顶 点 ， 为 拓扑 排 序 序 列 中 最 后 一 个 顶 点 。因 此 ， 按 退 出 DFS函 数 的 先 后 记 录 下 来 的 顶 点 序 列即 为 逆 向 的 拓 扑 排 序 序 列 。结 论 ： 拓 扑 排 序 -方 法 2 void DFS-ToplogicalSort () int v； for (v=0; vvexNum; +v) vertexsv.visited = false; / 访 问 标 志 初 始 化 Stack S; /存 放 顶 点 ， 按 照 出 DFS的 次 序 for (v=0; v=0; w=NextAdjVex(v,w) if (!vertexsw.visited) DFS-T(w); / 对 v的 尚 未 访 问 的 邻 接 顶 点 w递 归 调 用 DFS-T S.push(v); /顶 点 v的 DFS函 数 执 行 完 毕 / DFS-T 拓 扑 排 序 -方 法 2 a cgb dh f e写 出 下 图 的 所 有 的 拓 扑 序 列 拓 扑 排 序 -练 习 写 出 下 图 的 所 有 的 拓 扑 序 列 拓 扑 排 序 -练 习v1v3 v2 v5v6 v7v4 小 结 和 作 业拓 扑 排 序 1.什 么 是 拓 扑 排 序3. 拓 扑 排 序 算 法 2.如 何 进 行 拓 扑 排 序 作 业 ： P273, 9.1 , 9.3, 9.41