最小生成树实验报告Word文件下载.docx
《最小生成树实验报告Word文件下载.docx》由会员分享，可在线阅读，更多相关《最小生成树实验报告Word文件下载.docx（6页珍藏版）》请在冰点文库上搜索。
1.
2.i=n-1结束，否则转c。
3.设已经选择的边为e1,e2,……，ei,在G中选取不同于e1,e2,……ei的边，使｛e1,e2,……，ei,ei+1｝中无回路且ei+1是满足此条件的最小边。
4.iß
i+1，转b。
根据这个，还有以下思路：
由G生成的最小生成树T所包含的边的集合
1．按非降序权重将E中的边排序
2．建立n个单元素集（每个顶点一个）
3．最小生成树的边集合T初始为空
4.while|T|<
n-1
5.令e（x,y）为E中的下一条边
6.if包含x的集合不是与包含y的集合不是同一个集合then
7.将e（x,y）加入到T
8.将包含x的集合和包含y的集合合并
9.endif
10.endwhile
五、实验源代码及分析
#include<
stdio.h>
structEdge
{
intfrom,to,weight;
//定义一个数据结构，存放点和边的关系以及边的权值
};
Edgeedge[100],temp;
//用定义的数据结构来定义一个数组和一个变量
inti,j,n,m;
intp[100];
intseek（intx）//用来找出当前端点所在集合编号
if（p[x]==x）
returnx;
else
returnp[x]=seek（p[x]）;
}
IntKruskal（）
intx,y,k=0;
for（i=0;
i<
100;
i++）
p[i]=i;
m;
i++）
{
x=seek（edge[k].from）;
//找出当前边两个端点所在集合编号
y=seek（edge[k].to）;
if（x!
=y）//如果在不同集合，合并
{
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条边
Pleaseinputtheedgesanditsweight:
for（i=0;
{
scanf（"
%d%d%d"
edge[i].from,&
edge[i].to,&
edge[i].weight）;
//输入每一条边的起点、终点和权值
}
m-1;
i++）//对边的权值进行从小到大的排列
for（j=i+1;
j<
j++）
if（edge[i].weight>
edge[j].weight）
{
temp=edge[i];
edge[i]=edge[j];
edge[j]=temp;
}
printf（"
Theminimumspanningtreeis:
Kruskal（）;
//调用Kruskal算法
return0;
其中运用seek函数找出当前端点所在集合编号。
运用Kruskal函数来实现求出最小生成树的边，并且依次输出。
在主函数中将各个边按照权值的大小由小到大排序。
六、输入和输出及结果的分析
程序要求先输入结点个数以及边的个数，然后再依次输入各边的起点终点以及权值。
输出时则是输出最小生成树的边的起点终点和权值。
测试用例一：
老师的用例。
我们应该输入：
8，13然后输入123，232，383，872，762，612，141，252，534，273，472，571
其输入如图：
其输出如图：
测试用例二：
输入58；
然后输入121，232，342，453，512，143，521，242，如图所示：
输出也是如下图所示：
经过计算可以得知程序输出和理论上的计算完全一致，实验成功。
七、实验总结
通过这次求最小生成树的实验，提高了我的动手编程能力，学会了使用Kruskal算法求最小生成树，也加深了对离散数学书上最小生成树的理解。
5
升级会员 