nq8__数据结构算法分析-12.ppt

（0,0,0）(2,1,5)(0,2,1)(5,3,2)(1,4,3)(2,5,4) 第九章 图 9.1 图的基本概念 9.2 图的存储结构 9.3 图的遍历 9.4 拓扑排序和 关键路径 9.4.1 拓扑排序 9.5 最小代价生成树 9.5.1 普里姆算法 9.5.2 Kruscal 9.6 最短路径 9.5.2 克鲁斯卡尔算法 最小代价生成树的另一种算法。通过找n-1条不构成回路的最小权值边，来得到最小代价生成树。 设G=(V,E)是带权的连通图，T=(V’,E’)是正在构造中的生成树(构造之前是生成森林)。初始状态下，这个生成森林包含n棵只有一个结点的树，没有边，即V’=V，E’={ }。 从初始状态开始，重复执行下列运算： (1)在E中选一条权值最小的边(u,v)，并从E中删除； (2)若在T中加入(u,v)后不形成回路，则加入T； 重复(1)、(2)，直到E中包含n-1条边为止。 这时T=(V’,E’)是图G的一棵最小代价生成树。 1.克鲁斯卡尔算法(Kruscal) 2.克鲁斯卡尔算法实例 0 2 1 3 4 5 1 0 2 1 3 4 5 0 2 1 3 4 5 1 2 0 2 1 3 4 5 1 2 3 0 2 1 3 4 5 1 2 3 4 0 2 1 3 4 5 1 2 3 4 5 9.6 最短路径 第九章 图 9.1 图的基本概念 9.2 图的存储结构 9.3 图的遍历 9.4 拓扑排序和 关键路径 9.4.1 拓扑排序 9.5 最小代价生成树 9.5.1 普里姆算法 9.5.2 Kruscal 9.6 最短路径 最短路径是又一种重要的图算法。在生活中常常遇到这样的问题，两地之间是否有路可通？在有几条通路的情况下，哪一条路最短？这就是路由选择。 邮政自动分拣机的路选装置 计算机网络的路由选择 两种最常见的最短路径算法： 求单源最短路径的迪杰斯特拉（Djikstra）算法、求所有顶点之间的最短路径的弗洛伊德（ Floyd）算法。 注意这里所指的路径长度是指路径上的边所带的权值之和，而不是前面定义的路径上的边的数目。 9.6.1 单源最短路径 1.单源最短路径问题 给定带权的有向图G=(V,E)，源点v?V，求从顶点v到顶点集V中其余各顶点的最短路径。 2. Dijkstra算法 首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有顶点之间的最短路径都已求得为止。 3. Dijkstra算法用到的数据结构 (1) 图用邻接矩阵； (2) 集合S: 存放已经求得的最短路径的终点。初始状态时，集合S中只有一个源点。 (3) 一维数组d：保存各条最短路径的长度，其中，d[i]存放从顶点v0到顶点vi的最短路径长度。在算法执行中，若vi是尚未产生最短路径的顶点，则d[i]被定义为“由已经产生的最短路径上再扩充一条边”所形成的从v0到vi的“当前最短路径”。 (4) 一维数组path：指示该条最短路径。 path[i]给出从v0到vi的最短路径上顶点vi前面的那些顶点。 例如，从v0到v1的最短路径为（v0,v2,v3,v1） 则有path[1]=3，path[3]=2，path[2]=0。 4.Dijkstra算法 初始化 （1）集合S={ v0 } （2）d[i] （3）path[i]: 若v0,vi?E，则 path[i]=0，否则 path[i]=-1 for (int i=0;in;i++){ s[i]=false; d[i]=a[v][i]; if (i!=v d[i]NoEdge) path[i]=v; else path[i]=-1; } * 9.4 拓扑排序与关键路径 第九章 图 9.1 图的基本概念 9.2 图的存储结构 9.3 图的遍历 9.4 拓扑排序与关键路径 9.5 最小代价生成树 9.6 最短路径 内容提要： 从本节开始讨论图数据结构的应用，包括拓扑排序与关键路径、最小代价生成树和最短路径。 9.4.1 拓扑排序 一、AOV网络 拓扑排序是求解网络问题所需的主要算法，PERT (计划评审技术)和CMP(关键路径法)都要用到。 通常，一个工程(如软件开发、施工、生产流程等)可以分成若干子工程(称为活动)。要完成整个工程，就要完成所有活动。而活动的执行通常有某些先决条件的，即一些活动必须先于另一些活动完成。 用有向图可以表示活动的领先关系。 顶点：表示活动。 有向边：表示先决条件。 A