2022年最小生成树 .pdf
最小生成树 (Prim) 1、问题的提出假设要在n 个城市之间建立通信联络网，则连通n个城市只需要n-1 条线路，如何选择这 n-1 条线路，使这个建设费用最低。在每个城市之间都可以建立设置一条线路，相应地都要付出一定的经济代价。n 个城市之间，最多可能设置n(n-1)/2 条线路，那么，如何选择这些可能的线路中n-1 条，使总的耗费最少呢？可以用连通网来表示n 个城市以及n 个城市之间可能设置的通信线路，其中网的顶点表示城市， 边表示两个城市之间的线路，赋于边的权值表示相应的代价。对于 n 个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样的一棵生成树， 也就是使总的耗费最少。这个问题就是构成连通网的最小代价生成树 （简称最小生成树 ） 。2、最小生成树原理构造最小生成树可以有多种算法。其中多数算法都利用了最小生成树的下列一种简称为MST 的性质。MST ：假设 N=(V,E) 是一个连通网，U 是顶点集 V 的一个非空子集。若（u，v）是一条具有最小权值（代价）的边，其中,uUvVU ,则必存在一棵包含边（u，v）的最小生成树。反证法：假设网N 的任一棵最小生成树都不包含(,)u v。设 T 是连通网上的一棵最小生成树，当将（ u，v）加入到 T 中时，由生成树的定义，T 中必存在一条包含（u，v）的回路。另一方面，由于T 是生成树，则在T 上必存在另一条边(,)uv（u和u不一定是同一个点，v和v也不一定是同一个点） ，其中,uU vVU ，且 u 和u ，v 和v 之间均有路径相通。删去边(,)uv，便可消除上述回路，同时得到另一棵生成树T。因为 (, )u v 的代价不高于(,)uv的代价，则T的代价不高于T 的代价，T是包含 ( , )u v 的一棵最小生成树。由此和假设矛盾。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 3、Prim 算法假 设(, )NVE是 连 通 网 ，TE是 N 上 的 最 小 生 成 树 中 边 的 集 合 。 算 法 从00|,UuuVTE开 始 ， 重 复 执 行 下 述 操 作 ： 在 所 有,uUvVU 的 边(,)u vE中找一条代价最小的边00(,)uv并入集合TE，同时0v 并入 U ，直到 UV 为止。此时TE必有 n-1 条边，则(,)TVTE为 N 的最小生成树。4、Prim 算法 C 代码为了实现这个算法需附设一个辅助数组closedge，记录从 U 到VU 具有最小代价的边。对 每个顶点ivVU ，在辅助数组中存在一个相应分量closedgei-1 （表示 VU 中的点 ） ，它包括两个域，其中adjvex 域存储 该边依附的在U 中的顶点 。Lowcost 存储该边上的权值，显然：1.coscos(,) |iclosedgeilowtMint u vuUvoidminispantree(mgraph g, vertextypeu) inti , j , k, m ; struct vertextypeadjvex ; vrtypelowcost ; closedge MAX_VERTEX_NUM; k=locatevex( g,u); for ( j =0; j g. vexnum; j +)/ 辅助数组初始化if ( j != k) closedge j . adjvex =u; closedge j . lowcost =g.arcs k j . adj ; closedge k. lowcost =0;/ 初始 ,U=u for ( i =1; i g. vexnum; i +) / 选择其余 G.vexnum-1个顶点 / 下列两个 for 循环求出 T的下一个节点，第k个节点for ( m =0;m g. vexnum; m +) if ( closedge m . lowcost !=0) k=m ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - for ( m =0;m closedge m . lowcost ) k=m ; cout closedge k. adjvex g. vexs k endl ; closedge k. lowcost =0;/ 第k个顶点如 U集合for ( j =0;j g. vexnum; j +) if ( g. arcs k j . adj closedge j . lowcost ) / 新顶点并入 U后重新计算各边的最小值closedge j . adjvex =g. vexs k; closedge j . lowcost =g. arcs k j . adj ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -
