山西大学计算机与信息技术学院实验报告

山西大学计算机与信息技术学院实验报告姓名学号专业班级课程名称数据结构实验日期成绩指导教师批改日期实验名称最小生成树问题一、实验目的：为了更好地掌握生成树和图的结构特点和上机实现，掌握各种遍历方法。二、实验内容:1.概要设计若要在n个城市之间建立通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网络，这是一个网的最小生成树问题。利用克鲁斯卡尔算法求网的最小生成树。实现抽象数据类型的定义。2.详细设计#include<stdio.h>#include<stdlib.h>#defineM20#defineMAX20typedefstruct{intbegin;intend;intweight;}edge;typedefstruct{intadj;intweight;}AdjMatrix[MAX][MAX];typedefstruct{AdjMatrixarc;intvexnum,arcnum;}MGraph;voidCreatGraph(MGraph*);voidsort(edge*,MGraph*);voidMiniSpanTree(MGraph*);intFind(int*,int);voidSwapn(edge*,int,int);voidCreatGraph(MGraph*G){inti,j,n,m;printf("请输入边数和顶点数:\n");scanf("%d%d",&G->arcnum,&G->vexnum);for(i=1;i<=G->vexnum;i++){for(j=1;j<=G->vexnum;j++){G->arc[i][j].adj=G->arc[j][i].adj=0;}}for(i=1;i<=G->arcnum;i++){printf("请输入有边的2个顶点\n");scanf("%d%d",&n,&m);while(n<0||n>G->vexnum||m<0||n>G->vexnum){printf("输入的数字不符合要求请重新输入:\n");scanf("%d%d",&n,&m);}G->arc[n][m].adj=G->arc[m][n].adj=1;getchar();printf("请输入%d与%d之间的权值:\n",n,m);scanf("%d",&G->arc[n][m].weight);}printf("邻接矩阵为:\n");for(i=1;i<=G->vexnum;i++){for(j=1;j<=G->vexnum;j++){printf("%d",G->arc[i][j].adj);}printf("\n");}}voidsort(edgeedges[],MGraph*G){inti,j;for(i=1;i<G->arcnum;i++){for(j=i+1;j<=G->arcnum;j++){if(edges[i].weight>edges[j].weight){Swapn(edges,i,j);}}}printf("权排序之后的为:\n");for(i=1;i<G->arcnum;i++){printf("<<%d,%d>>%d\n",edges[i].begin,edges[i].end,edges[i].weight);}}voidSwapn(edge*edges,inti,intj){inttemp;temp=edges[i].begin;edges[i].begin=edges[j].begin;edges[j].begin=temp;temp=edges[i].end;edges[i].end=edges[j].end;edges[j].end=temp;temp=edges[i].weight;edges[i].weight=edges[j].weight;edges[j].weight=temp;}voidMiniSpanTree(MGraph*G){inti,j,n,m;intk=1;intparent[M];edgeedges[M];for(i=1;i<G->vexnum;i++){for(j=i+1;j<=G->vexnum;j++){if(G->arc[i][j].adj==1){edges[k].begin=i;edges[k].end=j;edges[k].weight=G->arc[i][j].weight;k++;}}}sort(edges,G);for(i=1;i<=G->arcnum;i++){parent[i]=0;}printf("最小生成树为:\n");for(i=1;i<=G->arcnum;i++){n=Find(parent,edges[i].begin);m=Find(parent,edges[i].end);if(n!=m){parent[m]=n;printf("<<%d,%d>>%d\n",edges[i].begin,edges[i].end,edges[i].weight);}}}intFind(int*parent,intf){while(parent[f]>0){f=parent[f];}returnf;}intmain(void){MGraph*G;G=(MGraph*)malloc(sizeof(MGraph));if(G==NULL){printf("memor