最小生成树实验报告Word文件下载.docx
- 文档编号:6983515
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:6
- 大小:171.34KB
最小生成树实验报告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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最小 生成 实验 报告