数据结构论文最小生成树

课题：最小生成树问题任课老师：朱节中专业：软件工程年级：2012级班级：1班学号：20122344001姓名：董上琦目录1.设计题目2.需求分析1）运行环境2）输入的形式和输入值的范围3）输出的形式描述4）功能描述5）测试数据3.概要设计1）抽象数据类型定义描述.2）功能模块设计3）模块层次调用关系图4.详细设计。实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法5.调试分析。包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会6.用户使用说明。详细列出每一步的操作说明7.测试结果8.附录：程序设计源代码1一、设计题目1).问题描述在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。2).基本要求以邻接多重表存储无向带权图，利用克鲁斯卡尔算法或普瑞姆算法求网的最小生成树。二、需求分析1）运行环境软件在JDK运行，硬件支持windows系统2）输入的形式和输入值的范围自动生成顶点数据在10~20之间；各个顶点之间权值在25~50之间；通过程序改动亦可生成已知顶点权值之间的最小生成树，需将随机生成代码改为edgeedge[]={newedge(0,1,16),new（0,2,18）......}；将已知顶点、权值通过其函数输入再生成其所对应最小生成树。3）输出的形式描述输出随机生成顶点个数以及各个顶点之间权值；然后输出本次生成顶点之间构成的最小生成树。4）功能描述该程序会自动生成介于10~20个数顶点模拟各城市，再随机生成介于25~50之间数值作为权值模拟各个城市间的距离，并同时生成此次顶点、权值相对应的最小生成树，模拟各城市间的最小距离，最小生成树。如有确定城市顶点及其权值，则可改动程序令其不再随机生成顶点权值，在程序中输入如下代码:edgeedge[]={newedge(0,1,16),new（0,2,18）......}输入数组为edge数组，edge（起点，终点，权值）。通过将随机生成代码改动就可以生成该城市对应权值的最小生成树。5）测试数据生成数据之后检验生成顶点数值是否介于10~20之间；检验各顶点间权值大小是否介于25~50间；同时检验其自动生成最小生成树是否正确。2三、概要设计1）抽象数据类型定义描述定义排序类sort，将各个顶点按照其两顶点之间权值大小排序，从大到小排序，用到堆排序算法；定义带权值的边edge，分别存在start（起点）、end（终点）、value(权值)三个变量；定义main类，调用sort、edge类与自身函数通过Kruskal函数实现最小生成树。2）功能模块设计主函数随机生成10~20个顶点作为城市并同时生成任意两顶点间25~50的权值作为两城市距离；在界面输出随机生成顶点个数及任意两顶点间权值；再调用sort函数对权进行排序，按照权值的大小有小到大排序；排序之后实现Kruskal函数，通过kruskal函数生成最小生成树；最后输出所生成的最小生成树。3）模块层次调用关系图3四、详细设计实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。1.定义带权值的边及其三个变量start（起点）、end（终点）、value（权值）；定义该属性为下边的根据权值排序、Kruskal实现最小生成树做下铺垫；函数实现如下：packagetree;publicclasssort{publicstaticvoidsift(edgea[],introot,intlimit){inti=root;intj=i*2+1;//j为i的左孩子while(j=limit)//沿较小值孩子节点向下筛选{if(jlimit&&a[j].getValue()a[j+1].getValue())//数组元素比较{j++;//j为左右孩子的较小者}if(a[j].getValue()a[i].getValue())//若父亲节点值较大{edgee=a[i];//孩子节点中较小值上移a[i]=a[j];a[j]=e;i=j;j=i*2+1;//i、j向下一层}else{break;//跳出循环}}}publicstaticvoidsort(edgedata[]){intlength=data.length;4for(inti=length/2-1;i=0;i--)//创建最大堆{sift(data,i,length-1);}for(intj=length-1;j0;j--)//每趟把最大值交换到后面字，再生成堆{edgee=data[0];data[0]=data[j];data[j]=e;sift(data,0,j-1);}}}2.随机生成介于10~20之间个顶点作为各个城市，并同时生成任意两顶点间权值，介于25~50之间；每n个顶点之间最多生成n*(n-1)条边；生成vertexNumber-1个row（行）和row-1个column（列）可以防止同一个顶点生成自环；函数实现如下：intvertexNumber=(int)((Math.random()+1)*10);System.out.println(随机生成+vertexNumber+个顶点);edgeedges[]=newedge[vertexNumber*(vertexNumber-1)/2];for(introw=0,index=0;rowvertexNumber;row++){//row行、column列、index数组for(intcolumn=0;columnrow;column++){intx=(int)((Math.random()+1)*25);//random随机的edges[index]=newedge(row,column,x);System.out.println(顶点+row+和+column+之间的距离为+x);index++;}}3.定义排序类sort，按照堆排序函数对数组edge[]按照权值大小从小到大进行排序（参照课本299页）；packagetree;publicclasssort{5publicstaticvoidsift(edgea[],introot,intlimit){inti=root;intj=i*2+1;//j为i的左孩子while(j=limit)//沿较小值孩子节点向下筛选{if(jlimit&&a[j].getValue()a[j+1].getValue())//数组元素比较{j++;//j为左右孩子的较小者}if(a[j].getValue()a[i].getValue())//若父亲节点值较大{edgee=a[i];//孩子节点中较小值上移a[i]=a[j];a[j]=e;i=j;j=i*2+1;//i、j向下一层}else{break;//跳出循环}}}publicstaticvoidsort(edgedata[]){intlength=data.length;for(inti=length/2-1;i=0;i--)//创建最大堆{sift(data,i,length-1);}for(intj=length-1;j0;j--)//每趟把最大值交换到后面字，再生成堆{edgee=data[0];data[0]=data[j];data[j]=e;6sift(data,0,j-1);}}}4.Kruskal方法实现最小生成树。Kruskal方法与Prim方法都是基于最小生成树的MST性质：设G(V,E)是一个联通带权无向图，TV是顶点集合V的一个非空真子集。若（tv，v）包含于E是一条权值最小的边，其中tv包含于TV，v包含于V-TV，则必定存在G的一棵最小生成树T,T包含边(tv,v)。其Kruskal算法参照课本334页。其算法如下：inta[]=newint[vertexNumber];//初始时刻，所有顶点的连通分量编号为-1，表示所有顶点都属于一个独立的连通分量for(inti=0;ia.length;i++){a[i]=-1;}edgeresult[]=newedge[vertexNumber-1];//该数组用于记录最小生成树inttemp=0;for(edgee:edges){intstart=e.getStart();intend=e.getEnd();if(a[start]==a[end]&&a[end]==-1){a[start]=a[end]=temp;result[temp]=e;temp++;}elseif(a[start]!=a[end]){if(a[start]==-1){a[start]=a[end];}elseif(a[end]==-1){a[end]=a[start];}else{intt=a[start];7for(inti=0;ivertexNumber;i++){if(a[i]==t){a[i]=a[end];}}}result[temp]=e;temp++;}五、调试分析包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会。Sort排序类算法时间复杂度为O（log2n），Kruskal算法时间复杂度为O(1)；调试过程中，Kruskal算法实现出现问题，刚开始无法实现该函数，无法生成最小生成树；经请教同学、查看资料、查看课本解决问题。实现堆排序过程无法实现，参考课本之后解得堆排序算法实现过程：调用sift（）方法n/2次，使得数据序列成为最大堆；对j=n-1，n-2...1，执行下列n-1次完成排序操作：交换根end[0]和元素end[j]，调用sift（）方法将end[j]的前j个元素调整成最大堆。在编程过程中如遇难题可对其题目进行认真分析，然后参考课本或者其他资料已现有代码亦或闻询他人帮助，在自己查询或者问询他人过程中也是自己学习的过程，可以从中学习到很多知识。六、用户使用说明程序运行后会自动跳出10~20个随机顶点作为各个城市，同时随机生成25~50的权值x，并生成此次所有顶点及其权值构成的最小生成树。七、测试结果1.生成0-12共13个顶点：82.生成最小生成树为：程序随机自动生成介于10~20之间个顶点正确运行，随机自动生成介于25~50之间权值正确运行，使得任意两顶点之间权值于25~50之间；经验证该生成树为最小生成树，程序运行正确。最小生成树定义：设G是一个带权连通无向图，w（e）是边e上的权，T是G的生成树，T中各边的权值之和称为生成树T的权值或者代价（cost）。权值最小的生成树称之为最小生成树（minimumcostspanningtree），简称最小生成树。9八、程序设计源代码packagetree;publicclasssort{publicstaticvoidsift(edgea[],introot,intlimit){inti=root;intj=i*2+1;//j为i的左孩子while(j=limit)//沿较小值孩子节点向下筛选{if(jlimit&&a[j].getValue()a[j+1].getValue())//数组元素比较{j++;//j为左右孩子的较小者}if(a[j].getValue()a[i].getValue())//若父亲节点值较大{edgee=a[i];//孩子节点中较小值上移a[i]=a[j];a[j]=e;i=j;j=i*2+1;//i、j向下一层}else{break;//跳出循环}}}publicstaticvoidsort(edgedata[]){intlength=data.length;for(inti=length/2-1;i=0;i--)//创建最大堆{sift(data,i,length-1);}10for(intj=length-1;j0;j--)//每趟把最大值交换到后面字，再生成堆{edgee=data[0];data[0]=data[j];data[j]=e;sift(data,0,j-1);}}}