数据结构-最小生成树实验报告

#include #include

#define MAXLEAF 100 #define INF 100000

#define EDGENUMBER MAXLEAF*MAXLEAF/2

typedef int EdgeType; typedef int VertexType;

typedef struct{ EdgeType val[MAXLEAF][MAXLEAF]; VertexType ves[MAXLEAF]; int v; int e; }MGraph;

typedef struct{ int vex1,vex2; int w; }kedge;

void creat_MGraph(MGraph *M){ int i,j,k; int w; printf(\"请输入图的顶点个数及边数：\\n\"); scanf(\"%d%d\ printf(\"请依次填充顶点信息：\\n\"); for(i=0;iv;i++) scanf(\"%d\ for(i=0;iv;i++) for(j=0;jv;j++) if(i==j) M->val[i][j]=0; else M->val[i][j]=INF; }

printf(\"请依次输入图的边两个顶点顶点的权值：(格式：a b c)\\n\"); for(k=0;ke;k++) { scanf(\"%d%d%d\ M->val[i-1][j-1]=w; M->val[j-1][i-1]=w; }

VertexType kruskal(MGraph M){ int tag[MAXLEAF]; kedge Ke[EDGENUMBER]; int i,j; VertexType length=0; int n=0; for(i=0;iKe[j+1].w){ temp=Ke[j+1]; Ke[j+1]=Ke[j]; Ke[j]=temp; } for(i=0;i%d: %d\\n\ tag[Ke[i].vex2]=first; for(j=0;jint main(){ MGraph M;

}

int len;

creat_MGraph(&M);

printf(\"最小生成树：\\n\"); len=kruskal(M);

printf(\"最小成本：%d\return 0;