《PRIM算法图的最小生成树求解》由会员分享，可在线阅读，更多相关《PRIM算法图的最小生成树求解（3页珍藏版）》请在装配图网上搜索。
1、MST的性质：假设N=（V,E）是一个连通图，条具有最小权值的边，其中u包含于生成树。更具体地说，我们维持一个集合U是顶点集V的一个非空子集。若口U,v包含于V-U,则必存在一颗包含皿S包含于V,在它上面已构造了到这步为止的生成u,v）是一u,v）的最小树，初始，S=s。每次迭代我们在S中增加一个结点，把结点v加入S能使“附加费用”min（e）=（u,v）:u属于S,C（e）达到最小，并且包含了在生成树中达到这个最小值的边e=（u,v）.这样解决此问题。2. 算法描述：从U=uOuO属于V,S=开始，重复执行下述步骤：属于E中找一条代价最小的边（uO,vO）并入集合中必有n1条边，则T=（V,
2、S）为G的最小生成树（3）结束3. 算法分析：在所有u属于U,v属于V-U的边（u,v)S,同时vO并入U,直到U=V为止，此时S普利姆算法算法是前人的劳动成果,是正确的,对于同一个图而言,普利姆算法的时间复杂度（n2），n为顶点数。三程序设计1程序设计的基本思路：。构造图函数,初始状态各个顶点都是独立的,知道所有的顶点以n-1条边连接即结束，生成最小生成树。2程序内部实现的说明。本程序采用嵌套及其循环调用的方法实现最小生成树。采用调用PRIM0000voidprim（）。根据PRIM00,将权排序，选择权最小的边,PRIM算法最小生成树求解二算法设计与分析：1.算法设计：构造最小生成树可以有
3、多种算法。其中多数算法利用了最小生成树的下列一种简称为流程图：最后生成树如下图所示步骤：权值分别为1,2,3,4,5的5条边由于满足上述条件依次输出,（书上的图）四测试结果及分析2分析总结：因此用PRIM00求出了最小生成树，及其的解。源代码#include#include#defineN100intpN,keyN,tbNN;voidprim(intv,intn)inti,j;intmin;for(i=1;i=n;i+)pi=v;keyi=tbvi;keyv=0;for(i=2;i=n;i+)min=INT_MAX;for(j=1;j0&keyjmin)v=j;min=keyj;printf(
4、%d%d,pv,v);keyv=0;for(j=1;j=n;j+)if(tbvjkeyj)pj=v,keyj=tbvj;intmain()intn,m;inti,j;intu,v,w;printf(分别输入顶点数，边数，各条路径权值：n);while(scanf(%d%d,&n,&m)for(i=1;i=n;i+)for(j=1;j=n;j+)tbij=INT_MAX;while(m-)scanf(%d%d%d,&u,&v,&w);tbuv=tbvu=w;printf(输出边路径：”)；prim(1,n);printf(n)；return0；输入顶点数，边数，各条路径权值及输出边路径实例一实例二实例三
PRIM算法图的最小生成树求解
