小生成树Prim算法.ppt

四、最小生成树四、最小生成树 ( minimum cost spanning tree )( minimum cost spanning tree ) 连通图G的一个子图如果是一棵包含G的所 有顶点的树，则该子图称为G的生成树。 生成树是连通图的极小连通子图。所谓 极小是指：若在树中任意增加一条边，则将 出现一个回路；若去掉一条边，将会使之变 成非连通图。 生成树各边的权值总和称为生成树的权 。权最小的生成树称为最小生成树 用不同的遍历图的方法，可以得到不同的生用不同的遍历图的方法，可以得到不同的生 成树；从不同的顶点出发，也可能得到不同的成树；从不同的顶点出发，也可能得到不同的 生成树。生成树。 按照生成树的定义，按照生成树的定义，n n 个顶点的连通网络的个顶点的连通网络的 生成树有生成树有 n n 个顶点、个顶点、n n - - 1 1 条边。条边。 构造最小生成树的准则：构造最小生成树的准则： n n 必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树； n n 必须使用且仅使用必须使用且仅使用 n n- -1 1 条边来联结网络中的条边来联结网络中的 n n 个顶点；个顶点； n n 不能使用产生回路的边。不能使用产生回路的边。 最小生成树（MST minimal spanning tree ）的重要 性质： 设 G =（V，E）是一个连通网络，U 是顶点 集 V 的一个非空子集。若（u，v）是一条具有最 小权值（代价）的边，其中uU,vV-U,则一定存 在 G 的一棵包括（u，v）的最小生成树。 uv UVU 证明（反证法）： 假设 G 中任何一棵最小生成树中都不包含 (u，v)。设T是一棵最小生成树但不包含(u，v) 。由于T是最小生成树，所以 T 是连通的，因 此有一条从u到v的路径，且该路径上必有一条 连接两个顶点集 U、V 的边(u，v)，其中uU ，vV-U。当把边(u，v)加入到 T 中后，得到 一个含有边(u，v)的回路。删除边(u，v)，上 述回路即被消除。由此得到另一棵生成树 T， T 和 T 的区别仅在于用边(u，v)代替了(u，v) 。由于(u，v)的权=(u，v)的全权，所以， T 的权=T的权，与假设矛盾。 uv U VU 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)(Prim)算法构造最小生成树的过程算法构造最小生成树的过程 1 2 3 4 65 5 6 5 1 7 32 54 6 1 2 3 4 65 5 1 32 4 从节点开始，选最小权值的边1，节点（，）入U; 从U中选最小权值边5，且对应节点不在U中，入U; 从U中选最小权值边3，且对应节点不在U中， 入U; 从U中选最小权值边4，且对应节点不在U中， 入U; 从U中选最小权值边2，且对应节点不在U中， 入U; 普里姆算法构造的基本思想普里姆算法构造的基本思想 为直观解释方便，设想在构造过程中，为直观解释方便，设想在构造过程中，T T的的 顶点集顶点集U U和边集均被涂成红色，和边集均被涂成红色，U U之外的顶点涂之外的顶点涂 成蓝色，连接红点和蓝点的边被涂成紫色。因成蓝色，连接红点和蓝点的边被涂成紫色。因 此，最短紫边就是连接此，最短紫边就是连接U U和和V-UV-U的最短边。的最短边。 设当前生成的设当前生成的T T有有k k个顶点，则当前紫边数目个顶点，则当前紫边数目 是是k(n-k)k(n-k)，紫边集过大。为了构造一个较小的紫边集过大。为了构造一个较小的 侯选紫边集，可以这样处理：对每一个蓝点，侯选紫边集，可以这样处理：对每一个蓝点， 从该蓝点到红点的紫边中，必有一条是最短的从该蓝点到红点的紫边中，必有一条是最短的 ，我们只要将所有，我们只要将所有n-kn-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) 调整侯选紫边集； (6) PRIM算法 typedef struct int fromvex,endvex; float length; edge; float distnn; edge Tn-1; PRIM() int j,k,m,v,min,max=10000; float d; edge e; for (j=1;jn;j+) Tj-1.fromvex=1; Tj-1.endvex=j+1; Tj-1.length=dist0j; for (k=0;kn-1;k+) min=max; for (j=k;jn-1;j+) if (Tj.lengthmin) min=Tj.length; m=j; e=Tm; Tm=Tk; Tk=e; v=Tk.endvex; for (j=k+1;jn-1;j+) d=distv-1Tj.endvex-1; if (