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

实验报告六（数学学院08级4班080204015余燕川）实验目的：通过对图的基本知识的学习，掌握图的基本概念，构造最小生成树，在此基础上上机实践，调试程序。实验题目：对一个给定的图G（V，E），构造最小生成树。三、实验分析：1、假设网G（V，E）是连通的，从顶点u出发构造G的最小生成树T，开始时，记T=（U，B），其中U是T顶点集合，B是T的边集合；2、开始时U={u0}(u0∈V)B=空,重复执行下述操作:在所有的u∈U,V∈V-U组成的边(u,v)中找出一条权值最小的边（u0,v0）并入边集B中,同时将v0加入顶点集U,直到U=V为止，此时T中必中必有n-1条边，则T=（U，B）为G的最小生成树。四、实验部骤：（1）构写程序的大体框架；（2）具体编写每个操作的程序；（3）程序的检查；（4）程序的调试；五、程序调试问题：输入顶点后，边的信息输不进去；如下图：六、实验结果：输入顶点数为5，边数为8，顶点为v1,v2,v3,v4,v5;后面出现了问题。七、实验程序：#defineMAXSIZE100#definemax10typedefchardatatype;typedefstruct{datatypevexs[MAXSIZE];intedges[MAXSIZE][MAXSIZE];intn,e;}graph;struct{charend;intlen;}minedge[max];voidCreatgraph(graph*ga){inti,j,k,w;printf("Pleaseputthenumberofgraph'svexsandedges:");scanf("%d,%d",&(ga->n),&(ga->e));printf("shuruidingdian:\n");for(i=0;i<ga->n;i++)scanf("%2c\n",&(ga->vexs[i]));for(i=0;i<ga->n;i++)for(j=0;j<ga->n;j++)ga->edges[i][j]=100;for(k=0;k<ga->e;k++){printf("shurui%dtiaobiandexuhaoi,jandquanzhiw:",k+1);scanf("%d,%d,%d\n",&i,&j,&w);ga->edges[i][j]=w;ga->edges[j][i]=w;}}voidprim(graph*g,charu){intv,k,j=0,min;for(v=1;v<=g->n;v++)if(v!=u){minedge[v].end=u;minedge[v].len=g->edges[v][u];}minedge[u].len=0;for(k=1;k<g->n;j++){min=minedge[k].len;v=j;}if(min==MAXSIZE){printf("error!");}printf("zuixiaoshengchengshu:");printf("%d%d",v,minedge[v].end);minedge[v].len=-minedge[v].len;for(j=1;j<=g->n;j++)if(g->edges[j][v]<minedge[j].len){minedge[j].len=g->edges[j][v];minedge[j].end=v;}}voidmain(){inti,j;graph*g;g=(grap