数据结构与算法六.ppt

即使不存在负的回路，也将出现后出现 的负权值，从而导致整体计算错误 主要原因是Dijstra算法是贪心法，当 作最小取进来后，不会返回去重新计算 支持负权值的最短路径算法 参考书MIT《Introduction to Algorithms》 6.5.2 每对顶点间的最短路径 以每个顶点为起点，调用|V|次Dijstra 算法 Void Dijkstra_P2P(Graph G) { Dist **D=new Dist *[G.VerticesNum()]; for(i=0; iG.VerticesNum();i++) D[i] = Dijkstra(Graph G,i); } Floyd算法的时间复杂度 三重for循环 复杂度是Θ(|V |3) 6.6 最小支撑树（ minimum-cost spanning tree，简称MST ） 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？ 问题： 构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。 该问题等价于： MST性质：设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中u ?U,v?V-U,则必存在一棵包含边(u,v)的最小生成树。 最小支撑树（minimum-cost spanning tree，简称MST） 对于带权的连通无向图G，其最小支撑树是一个包括G的所有顶点和部分边的图，这部分的边满足下列条件： （1）这部分的边能够保证图是连通的； （2）这部分的边，其权的总和最小。 算法二：（克鲁斯卡尔算法） 算法一：（普里姆算法） 6.6.1 Prim算法 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。 在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。 一般情况下所添加的顶点应满足下列条件: U V-U a b c d e g f 19 5 14 18 27 16 8 21 3 12 7 例如: a e d c b g f 14 8 5 3 16 21 所得生成树权值和 = 14+8+3+5+16+21 = 67 a b c d e g f 19 5 14 18 27 16 8 21 3 12 7 a e d c b a a a 19 14 18 14 例如: e 12 e e 8 16 8 d 3 d d 7 21 3 c 5 5 19 m m 14 m 18 19 5 7 12 m m m 5 3 m m m m 7 3 8 21 m 14 12 m 8 m 16 m m m 21 m 27 18 m m m 16 27 a b c d e f g a b c d e f g a b c d e f g 6.6.1 Prim算法（续） Prim算法与Dijkstra算法十分相似，唯一区别是： Prim算法要寻找的是离已加入顶点距离最近的顶点，而不是寻找离固定顶点距离最近的顶点 所以其时间复杂度分析与Dijkstra算法相同。 6.6.2 Kruskal算法 具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。 考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。 a b c d e g f 19 5 14 18 27 16 8 21 3 12 7 a e d c b g f 14 8 5 3 16 21 例如: 7 12 18 19 Kruskal算法代价 使用了路径压缩， 假设可能对几乎所有边都判断过了，则