最小生成树.ppt

四、最小生成树四、最小生成树( minimum cost spanning tree ) ( minimum cost spanning tree ) 连通图 G的一个子图如果是一棵包含 G的所有顶点的树,则该子图称为 G的生成树。生成树是连通图的极小连通子图。所谓极小是指:若在树中任意增加一条边, 则将出现一个回路;若去掉一条边,将会使之变成非连通图。生成树各边的权值总和称为生成树的权。权最小的生成树称为最小生成树用不同的遍历图的方法,可以得到不同的生成树;从不同的顶点出发,也可能得到不同的生成树。按照生成树的定义, n 个顶点的连通网络的生成树有 n 个顶点、 n-1 条边。构造最小生成树的准则: 必须只使用该网络中的边来构造最小生成树; 必须使用且仅使用 n-1 条边来联结网络中的 n 个顶点; 不能使用产生回路的边。最小生成树( MST minimal spanning tree )的重要性质: 设 G = (V,E)是一个连通网络, U 是顶点集 V 的一个非空子集。若( u, v)是一条具有最小权值(代价)的边,其中 u∈ U,v ∈ V-U, 则一定存在 G 的一棵包括( u,v)的最小生成树。 uv UV—U 证明(反证法): 假设 G 中任何一棵最小生成树中都不包含(u,v)。设 T是一棵最小生成树但不包含(u,v)。由于 T是最小生成树,所以 T 是连通的,因此有一条从 u到v的路径,且该路径上必有一条连接两个顶点集 U、 V 的边(u,v),其中 u∈U,v∈ V-U 。当把边(u,v) 加入到 T 中后,得到一个含有边(u,v)的回路。删除边(u,v),上述回路即被消除。由此得到另一棵生成树 T, T 和 T 的区别仅在于用边(u,v)代替了(u,v)。由于(u, v)的权<=(u ,v)的全权,所以, T的权<=T 的权,与假设矛盾。 uv U V—U uv普里姆普里姆(Prim) (Prim) 算法算法普里姆算法的基本思想: 普里姆算法的基本思想: 从连通网络从连通网络 N N = { = { V V, , E E } }中的某一顶点中的某一顶点 u u 0 0出出发,选择与它关联的具有最小权值的边发,选择与它关联的具有最小权值的边( (u u 0 0, , v v) ), , 将其顶点加入到将其顶点加入到生成树的顶点集合生成树的顶点集合 U U中。以后每中。以后每一步从一步从一个顶点在一个顶点在 U U中中,而,而另一个顶点不在另一个顶点不在 U U中中的各条边中选择的各条边中选择权值最小的边权值最小的边( (u u, , v v) ), ,把它的顶点把它的顶点加入到加入到集合集合 U U中。如此继续下去,直到网络中的中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合所有顶点都加入到生成树顶点集合 U U中为止。中为止。用普里姆(Prim) 算法构造最小生成树的过程 123 465 565 1732546 123 465 5 1324 从节点①开始,选最小权值的边 1,节点( ①,③)入 U; 从U中选最小权值边 5,且对应节点不在 U中, ②入 U; 从U中选最小权值边 3,且对应节点不在 U中, ⑤入 U; 从U中选最小权值边 4,且对应节点不在 U中, ⑥入 U; 从U中选最小权值边 2,且对应节点不在 U中, ④入 U; 普里姆算法构造的基本思想为直观解释方便,设想在构造过程中, T的顶点集 U和边集均被涂成红色, U之外的顶点涂成蓝色,连接红点和蓝点的边被涂成紫色。因此,最短紫边就是连接 U和 V-U 的最短边。设当前生成的 T有k个顶点,则当前紫边数目是 k(n-k) ,紫边集过大。为了构造一个较小的侯选紫边集,可以这样处理:对每一个蓝点, 从该蓝点到红点的紫边中,必有一条是最短的,我们只要将所有 n-k 个蓝点所关联的最短紫边作为侯选集,就必定能保证所有紫边中最短的紫边属于该侯选集。侯选集的调整方法: 当最短紫边(u,v) 被涂成红色被加入 T中后, v由蓝点变为红点,对每一个剩余的蓝点 j,边(v,j) 就由非紫边变成了紫边,这就使得我们必须对侯选集做如下调整:若侯选集中蓝点 j所关联的原最短紫边长度大于新紫边(v,j) 的长度,则以(v,j) 作为 j所关联的新的最短紫边来代替 j的原最短紫边,否则 j的原最短紫边不变。 Prim 算法的结构如下: (1) 置T为任意一个顶点,置初始侯选紫边集; (2) while ( T 中顶点数目<n) (3) { 从侯选紫边集中选取最短紫边(u,v); (4) 将 (u,v) 及蓝点 v 涂成红色,扩充到 T 中; (5)