prim算法求最小生成树（采用）.doc

《prim算法求最小生成树（采用）.doc》由会员分享，可在线阅读，更多相关《prim算法求最小生成树（采用）.doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、#include#include#defineMaxVertexNum30#defineINFINITY3000typedefstructcharvertexsMaxVertexNum;intarcsMaxVertexNumMaxVertexNum;intvertexNum,edgeNum;MGraph;typedefstructintadjvertex;intlowcost;ClosEdgeMaxVertexNum;voidCreatGraph(MGraph*G)inti,j,k,n;printf(请输入极点数跟边数：);scanf(%d%d,&(G-vertexNum),&(G-edgeN

2、um);printf(n);for(i=0;ivertexNum;i+)printf(请输入第%d个极点字符信息(共%d个)：,i+1,G-vertexNum);scanf(%c,&(G-vertexsi);getchar();for(i=0;ivertexNum;i+)for(j=0;jvertexNum;j+)if(i=j)G-arcsij=0;elseG-arcsij=999;for(k=0;kedgeNum);k+)printf(n);printf(请输入边对应的极点序号(共%d个)：,G-edgeNum);scanf(%d%d,&i,&j);printf(请输入此边的权值：);sca

3、nf(%d,&n);G-arcsij=n;G-arcsji=n;printf(n);printf(图已胜利创立!n);printf(n);voidMiniSpanTree_PRIM(MGraph*G,intu,ClosEdgeclosedge)inti,j,w,k;intcount=0;for(i=0;ivertexNum;i+)if(i!=u)closedgei.adjvertex=u;closedgei.lowcost=G-arcsui;closedgeu.lowcost=0;for(i=0;ivertexNum-1;i+)w=INFINITY;for(j=0;jvertexNum;j+)

4、if(closedgej.lowcost!=0&closedgej.lowcostw)w=closedgej.lowcost;k=j;closedgek.lowcost=0;for(j=0;jvertexNum;j+)if(G-arcskjarcskj;for(i=0;ivertexNum;i+)if(i!=u)printf(输入构建的最小天生树为：);printf(%d-%d,%dn,i,closedgei.adjvertex,G-arcsiclosedgei.adjvertex);count+=G-arcsiclosedgei.adjvertex;printf(n);printf(此最小天生树的价值为：%d,count);printf(n);voidmain()MGraph*G;intu;ClosEdgeclosedge;G=(MGraph*)malloc(sizeof(MGraph);CreatGraph(G);printf(输入结构最小天生树的动身极点：);scanf(%d,&u);printf(n);MiniSpanTree_PRIM(G,u,closedge);printf(n);