小生成树Prim算法

《小生成树Prim算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、四、最小生成树(minimumcostspanningtree)连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。生成树各边的权值总和称为生成树的权。权最小的生成树称为最小生成树用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。构造最小生成树的准则：必须只使用该网

2、络中的边来构造最小生成树；必须使用且仅使用n-1条边来联结网络中的n个顶点；不能使用产生回路的边。最小生成树（MSTminimalspanningtree）的重要性质：设G=（V，E）是一个连通网络，U是顶点集V的一个非空子集。若（u，v）是一条具有最小权值（代价）的边，其中u∈U,v∈V-U,则一定存在G的一棵包括（u，v）的最小生成树。uvUV—U证明（反证法）：假设G中任何一棵最小生成树中都不包含(u，v)。设T是一棵最小生成树但不包含(u，v)。由于T是最小生成树，所以T是连通的，因此有一条从u到v的

3、路径，且该路径上必有一条连接两个顶点集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的权，与假设矛盾。uvUV—Uuv普里姆(Prim)算法普里姆算法的基本思想：从连通网络N={V,E}中的某一顶点u0出发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到生成树的顶点集合U

4、中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。用普里姆(Prim)算法构造最小生成树的过程123465565173254612346551324从节点①开始，选最小权值的边1，节点（①，③）入U;从U中选最小权值边5，且对应节点不在U中，②入U;从U中选最小权值边3，且对应节点不在U中，⑤入U;从U中选最小权值边4，且对应节点不在U中，⑥入U;从U中选最小权值边2，且对应节点

5、不在U中，④入U;普里姆算法构造的基本思想为直观解释方便，设想在构造过程中，T的顶点集U和边集均被涂成红色，U之外的顶点涂成蓝色，连接红点和蓝点的边被涂成紫色。因此，最短紫边就是连接U和V-U的最短边。设当前生成的T有k个顶点，则当前紫边数目是k(n-k)，紫边集过大。为了构造一个较小的侯选紫边集，可以这样处理：对每一个蓝点，从该蓝点到红点的紫边中，必有一条是最短的，我们只要将所有n-k个蓝点所关联的最短紫边作为侯选集，就必定能保证所有紫边中最短的紫边属于该侯选集。侯选集的调整方法：当最短紫边(u,v)被涂成

6、红色被加入T中后，v由蓝点变为红点，对每一个剩余的蓝点j，边(v,j)就由非紫边变成了紫边，这就使得我们必须对侯选集做如下调整：若侯选集中蓝点j所关联的原最短紫边长度大于新紫边(v,j)的长度，则以(v,j)作为j所关联的新的最短紫边来代替j的原最短紫边，否则j的原最短紫边不变。Prim算法的结构如下：(1)置T为任意一个顶点，置初始侯选紫边集；(2)while(T中顶点数目

7、M算法typedefstruct{intfromvex,endvex;floatlength;}edge;floatdist[n][n];edgeT[n-1];PRIM(){intj,k,m,v,min,max=10000;floatd;edgee;for(j=1;j

8、ength