1、Prim算法.PDF

§7.4.2 最小生成树（Minimum Spanning Tree ） MST性质－大多数算法都利用了此性质 设G是连通图，G的生成树不唯一 设G ＝(V ，E) 是一连通图，U 是V 的真子集，若 （u ，v ）是所有连接U和V-U 的边中权最小的边 MST：权最小的生成树，树的权是各边上 （轻边），则一定存在G的一棵最小生成树包括此 的权值之和 边。 应用 Pf：设G的任何一棵最小生成树均不包括(u，v) ； n个城市之间的通信网，可构建n(n-1)/2条线路 n个城市连通至少要n-1条线路，G的生成树是 T’ 1个可行的方案 u v u 最小生成树是最经济的可行方案 v u’ T v’ u’ v’ U V-U 1 U V-U 2 构造MST： 1、Prim算法 就是找轻边扩充到当前生成的树T ＝（U，TE ）中 特点 U－红点集、红边集，构成T 当前形成的集合T ＝（U，TE ）始终是一棵树 V-U －白点集、白边集 T 中的顶点和边均为红色 紫边集－连接红点和白点的边 轻边－权最轻的紫边，或最短紫边(若权为长度): （u ，v ） 基本思想（贪心法） 1 1 设V(G)={0,1,…,n-1} 5 v u 1 1 算法的每一步均是在连接红、白点集的紫 50 u2 23 v2 边中选一轻边扩充到T （贪心），T从任意