数据结构最小生成树

1、#include<stdio.h> #include<stdlib.h>#define MAXLEAF 100#define INF 100000#define EDGENUMBER MAXLEAF*MAXLEAF/2typedef int EdgeType;typedef int VertexType;typedef structEdgeType valMAXLEAFMAXLEAF;VertexType vesMAXLEAF;int v;int e;MGraph;typedef structint vex1,vex2;int w;kedge;void creat_MG

2、raph(MGraph *M)int i,j,k;int w;printf(" 请输入图的顶点个数及边数： n"); scanf("%d%d",&(M->v),&(M->e);printf(" 请依次填充顶点信息： n"); for(i=0;i<M->v;i+) scanf("%d",&(M->vesi);for(i=0;i<M->v;i+)for(j=0;j<M->v;j+)if(i=j) M->valij=0;else M-&g

3、t;valij=INF;printf(" 请依次输入图的边两个顶点顶点的权值：(格式： i,j,w)n");for(k=0;k<M->e;k+)scanf("%d%d%d",&i,&j,&w);M->vali-1j-1=w;M->valj-1i-1=w;VertexType kruskal(MGraph M)int tagMAXLEAF;kedge KeEDGENUMBER;int i,j;VertexType length=0;int n=0;for(i=0;i<M.v;i+) tagi=i;for

4、(i=0;i<M.v;i+)for(j=i+1;j<M.v;j+)if(M.valij!=INF)Ken.vex1=i;Ken.vex2=j;Ken+.w=M.valij;kedge temp;for(i=0;i<n-1;i+)for(j=0;j<n-i-1;j+)if(Kej.w>Kej+1.w)temp=Kej+1;Kej+1=Kej;Kej=temp;for(i=0;i<n;i+)int first,second;first = tagKei.vex1;second = tagKei.vex2;if(first!=second)length+=Kei.

5、w;printf("%d->%d: %dn",Kei.vex1,Kei.vex2,Kei.w);tagKei.vex2=first;for(j=0;j<M.v;j+)if(second=tagj)tagj=first;return length;int main()MGraph M;int len;creat_MGraph(&M);printf(" 最小生成树： n");len=kruskal(M);printf(" 最短路径： %d",len);return 0;il tOC1231 Debug1231 .exe,t请输入图的顶点个数及边数：7 10谙依次填充顶点（r½:1 2 3 4 5 6 7诸依次输入图的边两个顶点顶点的权俏：（恪式：i1 3 621 2 503 7 502 5 455 6 653 4 853 4 524 7 564 5 533 6 36最小生成树:2-5: 361- >