文档介绍：:^112^012^117^610^6^0^4^3^0108^7129^0119^1^:假设要在n个城市之间建立通讯联络网,则连通n个城市只需要修建n-1条线路,如何在最节省经费的前提下建立这个通讯网?分析:最小生成树的定义:一个连通赋权图中代价最小的生成树,称为最小代价生成树,简称为最小生成树。最小生成树的MST性质设G=<V,E>是一个带权连通图,≠UV,若(u,v)是一条具有最小权值的边,其中u∈U,v∈U-V,则必定存在一棵包含边(u,v)的最小生成树。UV-Uuvu’v’证明:设G的任意一棵最小生成树T中均不包含边(u,v),则将边(u,v)加入T后将形成一个回路。如图所示:此时,从T树中删除边(u’,v’),然后加入边(u,v),将得到另外一棵生成树T’,T’的代价小于T的代价,即T’是包含边(u,v)的代价小于T的最小生成树,这于假设矛盾,故性质成立。一、Prim算法算法过程:设N=〈V,E〉为连通网,TE为N上最小生成树中边的集合。初值:U={u0|u0∈V};TE=;(u0,v0)={min(cost(u,v))|u∈U,v∈V-U},将边(u0,v0)并入TE,同时将点v0并入U;重复第2步,直至U=V为止,此时TE中有n-1条边,T=〈V,TE〉即为所求的最小生成树。实现分析: 算法的实现需要附设一个辅助向量closeedge,记录U到V-U具有最小代价的边:对V-U中的每个顶点vi,存在数组分量:closeedge[i].adjvexcloseedge[i].lowcostv3v2v4v5v66155536426v1v3v6v4v2v5v1Adjvexlowcost00000{v1,v3,v6,v4,V2,v5}23456UkAdjvexlowcostv16v11v15{v1}3Adjvexlowcostv350v15v36v34{v1,v3}6Adjvexlowcostv350v62v360{v1,v3,v6,}4Adjvexlowcostv3500v360{v1,v3,v6,v4}2Adjvexlowcost000v230{v1,v3,v6,v4,v2}5普里姆算法过程示例Prim算法(P175)VoidMiniSpanTree_Prim(MgraphG,VexTypeu){k=LocateVex(G,u);for(j=1;j<=;j++) if(j!=k)closeedge[i]={u,[k][j]};closeedge[k].lowcost=0;for(i=2;i<=;i++){ k=mininum(closeedge,);//找U和V-U的最小边的一个顶点 printf(closeedge[k].adjvex,[k]);//输出边 closeedge[k].lowcost=0;//置该顶点到集合U中 for(j=1;j<=;j++){ if{[k][j]<closeedge[j].lowcost) closeedge[j]={[k],[k][j];}//修改V-U中的每个顶点到U中的新距离}//for}//MiniSpanTree_Prim时间复杂度为O(n2),适合边稠密图。