您好,欢迎访问三七文档
北京理工大学软件学院一、实验目的1.通过上机程序,进一步加深对最小生成树的理解。2.掌握Kruskal算法。3.学会用程序解决离散数学中的问题。4.增强我们编写程序的能力。二、实验内容求带权无向联通平面图的最小生成树三、实验环境我的实验依旧是在VC6.0实验环境下完成的,而所设计的程序也在这个环境下通过了编译,运行和测试。四、实验原理和实现过程利用Kruskal算法求最小生成树,原理如下:1.选取最小权边e1,置边数j1.2.i=n-1结束,否则转c。3.设已经选择的边为e1,e2,……,ei,在G中选取不同于e1,e2,……ei的边,使{e1,e2,……,ei,ei+1}中无回路且ei+1是满足此条件的最小边。4.ii+1,转b。根据这个,还有以下思路:由G生成的最小生成树T所包含的边的集合1.按非降序权重将E中的边排序2.建立n个单元素集(每个顶点一个)3.最小生成树的边集合T初始为空4.while|T|n-15.令e(x,y)为E中的下一条边6.if包含x的集合不是与包含y的集合不是同一个集合then7.将e(x,y)加入到T8.将包含x的集合和包含y的集合合并9.endif实验2_最小生成树110.endwhile五、实验源代码及分析#includestdio.hstructEdge{intfrom,to,weight;//定义一个数据结构,存放点和边的关系以及边的权值};Edgeedge[100],temp;//用定义的数据结构来定义一个数组和一个变量inti,j,n,m;intp[100];intseek(intx)//用来找出当前端点所在集合编号{if(p[x]==x)returnx;elsereturnp[x]=seek(p[x]);}IntKruskal(){intx,y,k=0;for(i=0;i100;i++)p[i]=i;for(i=0;im;i++){x=seek(edge[k].from);//找出当前边两个端点所在集合编号y=seek(edge[k].to);if(x!=y)//如果在不同集合,合并实验2_最小生成树2{printf((%d,%d):%d\n,edge[k].from,edge[k].to,edge[k].weight);//输出这时的边的端点和权值p[x]=y;}k++;}return0;}intmain(){printf(Pleaseinputthenumberofthenodesandedges:\n);scanf(%d%d,&n,&m);//输入有n个节点m条边printf(Pleaseinputtheedgesanditsweight:\n);for(i=0;im;i++){scanf(%d%d%d,&edge[i].from,&edge[i].to,&edge[i].weight);//输入每一条边的起点、终点和权值}for(i=0;im-1;i++)//对边的权值进行从小到大的排列for(j=i+1;jm;j++)if(edge[i].weightedge[j].weight){temp=edge[i];edge[i]=edge[j];edge[j]=temp;}printf(Theminimumspanningtreeis:\n);实验2_最小生成树3Kruskal();//调用Kruskal算法return0;}其中运用seek函数找出当前端点所在集合编号。运用Kruskal函数来实现求出最小生成树的边,并且依次输出。在主函数中将各个边按照权值的大小由小到大排序。六、输入和输出及结果的分析程序要求先输入结点个数以及边的个数,然后再依次输入各边的起点终点以及权值。输出时则是输出最小生成树的边的起点终点和权值。测试用例一:老师的用例。我们应该输入:8,13然后输入123,232,383,872,762,612,141,252,534,273,472,571其输入如图:实验2_最小生成树4其输出如图:测试用例二:输入58;然后输入121,232,342,453,512,143,521,242,如图所示:实验2_最小生成树5输出也是如下图所示:经过计算可以得知程序输出和理论上的计算完全一致,实验成功。七、实验总结通过这次求最小生成树的实验,提高了我的动手编程能力,学会了使用Kruskal算法求最小生成树,也加深了对离散数学书上最小生成树的理解。
本文标题:最小生成树实验报告
链接地址:https://www.777doc.com/doc-5694101 .html