数据结构,第7章-5拓扑排序,ppt.ppt

* * DAG图 有向无环图（DAG图）是描述一项工程或系统进行过程的有效工具。 对于整个工程或系统而言，有两个核心问题： 工程能否顺序进行，即工程是否可行； 估算工程完成所需的最短时间。 对应于有向无环图就是进行拓扑排序和求关键路径。 一.什么是AOV网 验收 筹备 招标 备料 进驻 工地 测量 挖地基 浇注 水泥 搭架 子 … 例1 一个建筑工程 7.5 AOV网与拓扑排序 程序 语言 数据 结构 离散 数学 软件 工程 操作 系统 编译 原理 数据库 计算机 组成 汇编 网络 数字 逻辑 计算机 导论 例2 教学计划安排 二.AOV网的定义 以顶点表示活动，以有向边表示活动之间的 优先关系的有向图称为AOV网。 在AOV网中，若顶点i到 顶点j 之间存在有向路径，则称 顶点i 为顶点j 的前驱，顶点j 为顶点i的后继； 若顶点i 到 顶点j 之间存在一条有向边，则 称顶点i 为顶点j 的直接前驱， 顶点j 为顶点i 的直接后继。 A B C D F E 在AOV网中，如果活动Vi 必须在活动Vj 之前进行，则存在有向边Vi,Vj。 AOV网中不能出现有向回路，即有向环。在AOV网中如果出现了有向环，则意味着某项活动应以自己作为先决条件。 因此，对给定的AOV网，必须先判断它是否存在有向环。 数据 结构 程序设计 离散数学 回路 数据 结构 程序设计 离散数学 三.拓扑排序 3.如果通过拓扑排序能将AOV网的所有顶点都排入一个拓扑有序的序列中，则该AOV网中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网中存在有向环，即此AOV网所描述的工程是不可行的。 检查AOV网是否存在回路的方法是对AOV网进行 ，即构造一个AOV网的拓扑有序序列，使得该序列满足条件： 1. 若在AOV网中，顶点i优先于顶点j ,则在该序 列中也是顶点i优先于顶点j 。 2. 若在AOV网中，顶点i与顶点j之间不存在优 先关系,则在该序列中建立它们的优先关系，即顶点i 优先于顶点j，或顶点j优先于顶点i 。 拓扑排序 四.拓扑排序算法 前者说明AOV网中无回路， 后者说明AOV网中存在回路。 1. 从AOV网中任选择一个没有前驱(即入度为0)的顶点； 2. 从AOV网中删除该顶点以及以该顶点为始点的所有边； 3. 重复上述过程，直到网中的所有顶点都被删除,或者 网中还有顶点，但不存在入度为0 的顶点。