kruskal算法求图的最小生成树

《kruskal算法求图的最小生成树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、利用Kruskal算法求图的最小生成树程序设计2007-10-0922:23阅读160评论1字号：大大中中小小/*利用Kruskal算法求图的最小生成树(2007.8.7)*/#include#include#defineMaxVertexNum12#defineMaxEdgeNum20#defineMaxValue1000typedefintVertexType;typedefVertexTypevexlist[MaxVertexNum];typedefintadjmatrix[MaxVertexNum][M

2、axVertexNum];intvisited[MaxVertexNum]={0};structedgeElem{intfromvex;/*边的起点域*/intendvex;/*边的终点域*/intweight;/*边的权值域*/};typedefstructedgeElemedgeset[MaxEdgeNum];voidKruskal(edgesetGE,edgesetC,intn){inti,j,k,d,m1,m2;adjmatrixs;for(i=0;i

3、es[i][j]=0;}k=1;d=0;while(k

4、

5、s[m2][j];s[m2][j]=0;}}d++;}}voidCreate(vexlistGV,edgesetGE,intn,inte)/*建立顶点数组GV和边集数组GE*/{inti,j,k,w;pri

6、ntf("输入%d个顶点数据",n);for(i=0;i

7、dvex,GE[i].weight);printf("");}main(){intn,e;vexlistgv;adjmatrixga;edgesetge,c;printf("输入图的顶点数和边数:");scanf("%d%d",&n,&e);Create(gv,ge,n,e);printf("利用Kruskal算法从顶点0出发求图的最小生成树:");Kruskal(ge,c,n);outputEdgeset(c,n-1);getch();}/*输入图的顶点数和边数:610输入6个顶点数据012345输入10条无向带权边04412513823

8、10151235150118342005234525利用Kruskal算法从顶点0出发求图的最小生成树:044,125,138,1512,0118,*/