《数据结构与算法》prim算法求最小生成树（采用）.docx

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

1、数据结构与算法prim算法求最小生成树(采用)#include#include#define MaxVertexNum 30#dcfine INFINITY 3000typedef struct (char vcrtcxslMaxVcrtcxNuin;ini arcsMaxVei(exNumMaxVertexNuml;int vcrtcxNum,cdgeNum;JMGraph;typedef struct(int adj vertex;int lowcost;)ClosEdgeMaxVertexNum;void CreatGraph(MGraph *G) (int i,j,k,n;printf

2、(请输入顶点数和边数：”)；scanf(u%d %d,&(G-vertexNum),&(G-edgeNum);printf(n);for(i=0;ivcrtcxNum;i+) (printf(请输入第d个顶点字符信息(共d个)：J+l,G-vcrtcxNum);scanf(%cM,&(G-vertexsil);getchar();foi(i=0;ivertexNum;i+)for(j=0;jvcrtcxNum;j+)(if(i=j)G-arcsij=0;elseG-arcsij=999;)for(k=0:kedgeNum);k+)(printf(n);prindf请输入边对应的顶点序号(共d个

3、)：;G-edgeNum); scanf(%dprintf(请输入此边的权值：);scanf(%d,&n);G-arcsij=n;G-arcsjJli=n;printfCXn);prinlf(图已成功创建成) printf(n);)void MiniSpanTrcc_PRIM(MGraph *G,int u,ClosEdgc closcdgc) int i,j,w,k;int count=0;for(i=0;ivertexNum;i+)if(i!=u)closcdgci.adjvcrtcx=u;closedgei.lowcost=G-arcsui;Iclosedgeu.lowcost=0;fo

4、r(i=0;ivertexNum-1 ;i+)(w=INFINITY;for(j=0;jvcrtcxNum;j+)if(closedgej.lowcost! =0 & closedgej.lowcostw) (w=closedgejl. lowcost;k=j；)closedgek.lowcost=0;for(j=0;jvcrtcxNum;j+) if(G-arcskljlarcskj;1)for(i=0;ivertexNum;i+) if(i!=u)(printf(输出构建的最小生成树为：”)；printf(%d-%d,%dn,i,closedgei.adjvertex,G-arcsiclosedgei.adjvertex);count+=G-arcsijclosedgei.adj vertex J;printf(n);prinlf(此最小生成树的代价为：%d,count);printf(n);void main()(MGraph *G;int u;ClosEdge closedge;G=(MGraph*)malloc(sizeof(MGraph);CreatGraph(G);printf(输入构造最小生成树的出发顶点：);scanf(%d,&u);printf(n);MiniSpanTree_PRIM(G,u,closcdge);printf(n);