《数据结构与算法》prim算法求最小生成树（采用）.docx
数据结构与算法prim算法求最小生成树(采用)#include<stdio.h>#include<stdlib.h>#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("请输入顶点数和边数：”)；scanf(u%d %d",&(G->vertexNum),&(G->edgeNum);printf("n");for(i=0;i<G->vcrtcxNum;i+) (printf("请输入第d个顶点字符信息(共d个)："J+l,G->vcrtcxNum);scanf("%cM,&(G->vertexsil);getchar();foi(i=0;i<G->vertexNum;i+)for(j=0;j<G->vcrtcxNum;j+)(if(i=j)G->arcsij=0;elseG->arcsij=999;)for(k=0:k<(G->edgeNum);k+)(printf("n");prindf请输入边<Vi,Vj>对应的顶点序号(共d个)：'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;i<G->vertexNum;i+)if(i!=u)closcdgci.adjvcrtcx=u;closedgei.lowcost=G->arcsui;Iclosedgeu.lowcost=0;for(i=0;i<G->vertexNum-1 ;i+)(w=INFINITY;for(j=0;j<G->vcrtcxNum;j+)if(closedgej.lowcost! =0 && closedgej.lowcost<w) (w=closedgejl. lowcost;k=j；)closedgek.lowcost=0;for(j=0;j<G->vcrtcxNum;j+) if(G->arcskljl<closedgejl.lowcost) |closedgejl.adjverlex=k;closedgej.lowcost=G->arcskj;1)for(i=0;i<G->vertexNum;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");
