最小生成树实验报告.docx

一、实验目的通过上机程序,进一步加深对最小生成树的理解。掌握Kruskal算法。学会用程序解决离散数学中的问题。增强我们编写程序的能力。二、 实验内容求带权无向联通平面图的最小生成树三、 实验环境我的实验依旧是在实验环境下完成的,而所设计的程序也在这个环境下通过了编译,运行和测试。四、 实验原理和实现过程利用Kruskal算法求最小生成树,原理如下:选取最小权边el,-l结束,否则转c。设已经选择的边为el,e2, , ei,在G中选取不同于el,e2, ei的边,使{el,e2,……,ei,ei+l}中无回路且ei+1是满足此条件的最小边。ii+1,转b。根据这个,还有以下思路:由G生成的最小生成树T所包含的边的集合按非降序权重将E中的边排序建立n个单元素集(每个顶点一个))TI<n~l令e(x,y)为E中的下一条边辻包含x的集合不是与包含y的集合不是同一个集合then将e(x,y)、 实验源代码及分析#include〈>structEdge{intfrom,to,weight; rom);o):if(x!=y) rom,edge[k]・to,edge[k]・weight);rom,&edge[i]・to,&edge[i_・weight);eight>edge[j]・weight){temp二edge[i];edge[i]二edge[j];edge[j]二temp;}printf(,zTheminimumspanningtreeis:\n");Kruskal(); //调用Kruskal算法return0;}其中运用seek函数找出当前端点所在集合编号。运用Kruskal函数来实现求出最小生成树的边,并且依次输出。在主函数中将各个边按照权值的大小由小到大排序。六、 输入和输出及结果的分析程序要求先输入结点个数以及边的个数,然后再依次输入各边的起点终点以及权值。输出时则是输出最小生成树的边的起点终点和权值。测试用例一:老师的用例。我们应该输入:8,13然后输入123,232,383,872,762,612,141,252,□34,273,472,o71其输入如图:其输岀如图:测试用例二:输入5"D:\ProgramFiles\MicrosoftVisualStudio'MyProjects、最小生成赫Debug\^<]\'Pleaseinputthenunberofthenodesandedges:813Pleaseinputtheedgesanditsueight:1238732322「wD:\ProgramFiles\MicrosoftVisualStud6\