最小生成树算法讲解.ppt

西安电子科技大学软件学院 - School puter Software, Xidian University, China 1单元实验五------ 最小生成树西安电子科技大学软件学院 - School puter Software, Xidian University, China 2生成树的概念生成树一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的 n-1 条边。生成树不唯一 V 3V 2V 4V 1V 6V 5 V 3V 2V 4V 1V 6V 5V 3V 2V 4V 1V 6V 5V 3V 2V 4V 1V 6V 5生成树西安电子科技大学软件学院 - School puter Software, Xidian University, China 3最小代价生成树?生成树的代价等于其边上的权值之和。 V 4V 1V 3V 2V 6V 56 5 12 66 5534 V 4V 1V 3V 2V 6V 56 1 654 V 4V 1V 3V 2V 6V 512 534 西安电子科技大学软件学院 - School puter Software, Xidian University, China 4最小代价生成树?两种常用的构造最小生成树的方法: ?普里姆算法?克鲁斯卡尔算法西安电子科技大学软件学院 - School puter Software, Xidian University, China 5 ?假设 N=(V ,E)是连通网, TE是N上最小生成树中边的集合。?算法从 U={u 0}(u 0∈V),TE={} 开始,重复执行下述操作: ?在所有 u∈U,v∈V-U 的边(u,v)中找一条代价最小的边(u 0 ,v 0),将其并入集合 TE,同时将 v 0并入 U集合。?当U=V 则结束,此时 TE中必有 n-1 条边,则 T=(V ,{TE}) 为N的最小生成树。?普里姆算法构造最小生成树的过程是从一个顶点 U={u 0}作初态,不断寻找与 U中顶点相邻且代价最小的边的另一个顶点,扩充到 U集合直至 U=V 为止。普里姆(Prim) 算法西安电子科技大学软件学院 - School puter Software, Xidian University, China 6 V 4V 1V 3V 2V 6V 56 5 12 66 5534 V 4V 1V 3V 2V 6V 512 534U V-U {V 1}{V 2 ,V 3 ,V 4 , V 5 ,V 6} 步骤(0) {V 1 ,V 3}{V 2 ,V 4 , V 5 ,V 6} (1) {V 1 ,V 3 ,V 6}{V 2 ,V 4 , V 5} (2) {V 1 ,V 3 ,V 6 ,V 4}{V 2, V 5} (3) {V 1 ,V 3 ,V 6 ,V 4 ,V 2}{V 5} (4) {V 1 ,V 3 ,V 6 ,V 4 ,V 2 ,V 5}{} (5) 最小代价生成树普里姆算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止西安电子科技大学软件学院 - School puter Software, Xidian University, China 7 V 4V 1V 3V 2V 6V 51 65 V 1V 31{V 1}{V 2 ,V 3 ,V 4 , V 5 ,V 6} 步骤(0) {V 1 ,V 3}{V 2 ,V 4 , V 5 ,V 6} (1) U V-U 普里姆算法求最小生成树:从生成树中只有一个顶点开始,到顶点全部进入生成树为止最小代价生成树西安电子科技大学软件学院 - School puter Software, Xidian University, China 8 V 4V 1V 3V 2V 6V 5 65 V 1V 31{V 1}{V 2 ,V 3 ,V 4 , V 5 ,V 6} 步骤(0) {V 1 ,V 3}{V 2 ,V 4 , V 5 ,V 6} (1) V 6{V 1 ,V 3 ,V 6}{V 2 ,V 4 , V 5} (2) 4