《利用Kruskal算法求图的最小生成树.doc》由会员分享，可在线阅读，更多相关《利用Kruskal算法求图的最小生成树.doc（3页珍藏版）》请在三一文库上搜索。
1、利用Kruskal算法求图的最小生成树程序设计 2007-10-09 22:23 阅读160 评论1 字号： 大大 中中 小小 /*利用Kruskal算法求图的最小生成树(2007.8.7)*/#include#include#define MaxVertexNum 12#define MaxEdgeNum 20#define MaxValue 1000typedef int VertexType;typedef VertexType vexlistMaxVertexNum;typedef int adjmatrixMaxVertexNumMaxVertexNum;int visitedMax
2、VertexNum=0;struct edgeElem int fromvex; /*边的起点域*/ int endvex; /*边的终点域*/ int weight; /*边的权值域*/;typedef struct edgeElem edgesetMaxEdgeNum;void Kruskal(edgeset GE ,edgeset C,int n) int i,j,k,d,m1,m2; adjmatrix s; for(i=0;in;i+) for(j=0;jn;j+) if(i=j) sij=1; else sij=0; k=1; d=0; while(kn) for(i=0;in;i
3、+) if(siGEd.fromvex=1) m1=i; if(siGEd.endvex=1) m2=i; if(m1!=m2) Ck-1=GEd; k+; for(j=0;jn;j+) sm1j=sm1j|sm2j; sm2j=0; d+; void Create(vexlist GV,edgeset GE,int n,int e) /*建立顶点数组GV和边集数组GE*/ int i,j,k,w; printf(输入%d个顶点数据n,n); for(i=0;in;i+) scanf(%d,&GVi); printf(输入%d条带权边n,e); for(k=0;ke;k+) scanf(%d
4、%d %d,&i,&j,&w); GEk.fromvex=i; GEk.endvex=j; GEk.weight=w; void outputEdgeset(edgeset GE,int e) /*输出一个图的邻接矩阵*/ int i; for(i=0;ie;i+) printf(%d %d %d, ,GEi.fromvex, GEi.endvex,GEi.weight); printf(n);main() int n,e; vexlist gv; adjmatrix ga; edgeset ge,c; printf(输入图的顶点数和边数:); scanf(%d %d,&n,&e); Create(gv,ge,n,e); printf(利用Kruskal算法从顶点0出发求图的最小生成树:n); Kruskal(ge,c,n); outputEdgeset(c,n-1); getch();/*输入图的顶点数和边数:6 10输入6个顶点数据0 1 2 3 4 5输入10条无向带权边0 4 41 2 51 3 82 3 101 5 123 5 150 1 183 4 200 5 234 5 25利用Kruskal算法从顶点0出发求图的最小生成树:0 4 4, 1 2 5, 1 3 8, 1 5 12, 0 1 18,*/