数据结构－第07章－图_04.pptVIP

7.5 有向无环图及其应用 一个无环的有向图称做有向无环图，简称DAG图。 DAG图是用来描述一项工程或任务进行过程的有效工具，如学校可通过DAG图来描述和分析教学计划及课程的安排和实施。一项大的工程或任务常常可划分为许多较小的称为活动的子工程或子任务，而这些子工程之间通常受着一定条件的约束，如其中一些子工程的开始必须在另外一些子工程完成之后。 7.5.1 拓扑排序 偏序、全序 若集合X上的关系R是自反的、反对称的和传递的，则称只是集合X上的偏序关系。 设R是集合X上的偏序(Partial Order)，如果对每个x,y∈X必有xRy或yRx，则称R是集合X上的全序关系。 7.5.1 拓扑排序 数学定义： 设A是一个非空集，P是A上的一个关系，若P适合下列条件：（1）对任意的a∈A,(a,a)∈P;（2）若（a,b)∈P且（b,a)∈P,则a=b;（3）若（a,b)∈P,(b,a)∈P,则（a,c)∈P,则称P是A上的一个偏序关系。带偏序关系的集合A称为偏序集或半序集。 若P是A上的一个偏序关系，我们用a≤b来表示（a,b)∈P。全序：是P是集合A上的偏序关系，如果对每个x，y∈A，一定有xPy或者yPx，则称P是集合A的全序关系。 7.5.1 拓扑排序 直观地看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。 参考图7.25（P.180） 7.5.1 拓扑排序 AOV-网 用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网（aactivity on vertex network），简称AOV-网 7.5.1 拓扑排序 所谓拓扑排序就是对 AOV-网构造一线性序列使所有的优先关系在序列中得以体现，在AOV-网中不应该出现有向环回路，因为存在环意味着某项活动应以自己为先决条件，这样的工程是无法进行的。 7.5.1 拓扑排序 AOE-网 顶点表示事件，弧表示活动，权表示活动持续的时间。 关键路径 AOE网中从源点到汇点的最长路径长度所在的路径就叫做关键路径。 * 7.6 最短路径 兰州 太原 北京 济南 徐州 郑州 西安 旅客希望停靠站越少越好，则应选择 济南——北京——太原——兰州 旅客考虑的是旅程越短越好， 1120 920 720 210 540 340 640 190 济南——徐州——郑州——西安——兰州 带权图的最短路径计算问题 通常在实际中，航运、铁路、船行都具有有向性，故我们以带权有向图为例介绍最短路径算法。 带权无向图的最短路径算法也通用。 从单个源点到其余各顶点的最短路径算法。 每一对顶点之间的最短路径算法。 7.6.1 从单个源点到其余各顶点的最短路径算法 —— Dijkstra 算法 思想: 贪心算法(局部最优)，按路径长度递增的次序产生最短路径。 贪心算法: 利用局部最优来计算全局最优。 利用已得到的顶点的最短路径来计算其它顶点的最短路径。 例， v5 v0 v1 v4 v3 60 100 5 v2 10 30 20 10 50 求从 v0 到其余各顶点的最短路径。 1. 初始，D[i] 的值为 v0 到 vi 的弧的权值 D[i] 表示 v0 到 vi 的最短路径的长度 显然，D[i] 中的最小值 D[2] 便是 v0到 v2 的最短路径的长度，Path[2]=( v0 , v2 ) Path[i]表示v0 到 vi 的最短路径 * *