c语言实现最小生成树算法

《c语言实现最小生成树算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、最小生成树算法C语言代码如下：#include#include#defineTURE999typedefstructArcNode{charvexs[10];intedgs[10][10];intn,e;}MGraph;structedg{intv1;intv2;intcost;}A[10],B[10];//创建图voidGreateMGraph(MGraph*G){inti,j,k,weight,m,n;intch1,ch2;chara,b;printf("请输入顶点数和边数(格式如4):");scanf("%d%d",&(G->n),

2、&(G->e));//输入顶点数,边数for(i=0;in;i++){getchar();printf("请输入第%d个顶点:",i+1);scanf("%c",&(G->vexs[i]));//输入¨顶点}for(i=0;in;i++)for(j=0;jn;j++)G->edgs[i][j]=0;for(k=0;ke;k++){printf("请输入第%d条边的顶点权值(格式如¨ij):",k+1);getchar();scanf("%c%c%d",&a,&b,&weight);m=0;n=0;for(m=0;G->vexs[m]!=a;m++

3、);for(n=0;G->vexs[n]!=b;n++);ch1=m;ch2=n;G->edgs[ch1][ch2]=weight;G->edgs[ch2][ch1]=weight;}}voidprim(MGraph*G,intv){inti,j,k,min;struct{intadjvex;intlowcost;}closedge[10];for(i=0;in;i++){closedge[i].lowcost=G->edgs[v][i];closedge[i].adjvex=v;}closedge[v].lowcost=TURE;for(i=1;in;i++)

4、{min=100;for(j=0;jn;j++)if(closedge[j].lowcost!=TURE&&closedge[j].lowcost!=0){if(closedge[j].lowcostvexs[closedge[k].adjvex],G->vexs[k],min);closedge[k].lowcost=TURE;for(j=0;jn;j++)if(closedge[j].lowcost!=TURE)if(G->edgs[k][j

5、]

6、

7、closedge[j].lowcost==0){closedge[j].lowcost=G->edgs[k][j];closedge[j].adjvex=k;}}}intmain(void){MGraph*G,a;charch1;G=&a;printf("建立图的邻接矩阵");GreateMGraph(G);getchar();ch1=1;printf("");printf("最小生成树");printf("prim算法输出为a：");prim(G,0);system("pause");}运行结果截图：在线编译成功；