实验5最小生成树算法设计与实现.doc

该【实验5最小生成树算法设计与实现 】是由【夏天教育】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【实验5最小生成树算法设计与实现 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。(完好word版)实验5最小生成树算法的设计与实现(报告)
(完好word版)实验5最小生成树算法的设计与实现(报告)
1/9
(完好word版)实验5最小生成树算法的设计与实现(报告)
实验5最小生成树算法的设计与实现
一、实验目的
1、依据算法设计需要,掌握连通图的灵巧表示方法;
2、掌握最小生成树算法,如Prim、Kruskal算法;
3、基本掌握贪婪算法的一般设计方法;
4、进一步掌握会集的表示与操作算法的应用。
二、实验内容
1、认真阅读算法设计教材和数据结构教材内容,熟悉连通图的不一样表示方
法和最小生成树算法;
2、设计Kruskal算法实验程序。
有n个城市可以用(n-1)条路将它们连通,求最小总行程的和。
设计测试问题,更正并调试程序,输出最小生成树的各条边,直至正确为止。
三、Kruskal算法的原理方法
边权排序:
131
462
364
145
235
345
256
126
356
566
:属于最小生成树的极点U={}
不属于最小生成树的极点V={1,2,3,4,5,6}
依据边权排序,选出还没有连接而且权最小的边(131),属于最小生成树的极点U={1,3},不属于最小生成树的极点V={2,4,5,6}
(完好word版)实验5最小生成树算法的设计与实现(报告)
(完好word版)实验5最小生成树算法的设计与实现(报告)
2/9
(完好word版)实验5最小生成树算法的设计与实现(报告)
依据边权排序,选出还没有连接而且权最小的边(462),属于最小生成树的极点U={{1,3},{4,6}}(还没有合在一起,有两颗子树),不属于最小生成树的极点V={2,5}
依据边权排序,选出还没有连接而且权最小的边(364),属于最小生成树的极点U={1,3,4,6}(合在一起),不属于最小生成树的极点V={2,5}
(完好word版)实验5最小生成树算法的设计与实现(报告)
(完好word版)实验5最小生成树算法的设计与实现(报告)
3/9
(完好word版)实验5最小生成树算法的设计与实现(报告)
依据边权排序,选出还没有连接而且权最小的边(364),属于最小生成树的极点U={1,2,3,4,6},,不属于最小生成树的极点V={5}
,选出还没有连接而且权最小的边(364),属于最小生
(完好word版)实验5最小生成树算法的设计与实现(报告)
(完好word版)实验5最小生成树算法的设计与实现(报告)
4/9
(完好word版)实验5最小生成树算法的设计与实现(报告)
成树的极点U={1,2,3,4,5,6}此时,最小生成树已完成
(完好word版)实验5最小生成树算法的设计与实现(报告)
(完好word版)实验5最小生成树算法的设计与实现(报告)
9/9
(完好word版)实验5最小生成树算法的设计与实现(报告)
四、实验程序的功能模块
功能模块:
boolcmp(Edgea,Edgeb);//定义比较方法
intgetfa(intx);//在并查集丛林中找到x的先人
intsame(intx,inty);//判断先人是不是同一个,即能否联通
voidmerge(intx,inty);//合并子树,即联通两子树
sort(e+1,e+m+1,cmp);//对边按边权进行升序排序
详细代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#defineMAXN_E100000
#defineMAXN_V100000
usingnamespacestd;
structEdge{
(完好word版)实验5最小生成树算法的设计与实现(报告)
(完好word版)实验5最小生成树算法的设计与实现(报告)
6/9
(完好word版)实验5最小生成树算法的设计与实现(报告)
intfm,to,dist;//边的初步极点,边的到达极点,边权
}e[MAXN_E];
intfa[MAXN_V],n,m;//极点数组,极点总数,边总数
//定义比较,不过边权比较
boolcmp(Edgea,Edgeb){
<;
}
//查找x的先人
intgetfa(intx){//getfa是在并查集丛林中找到x的先人
if(fa[x]==x)returnfa[x];
elsereturnfa[x]=getfa(fa[x]);
}
//判断先人是不是同一个,即能否联通
intsame(intx,inty){
returngetfa(x)==getfa(y);
}
//合并两棵树
voidmerge(intx,inty){
intfax=getfa(x),fay=getfa(y);
fa[fax]=fay;
}
intmain( ){
inti;
cout<<"请输入极点数量和边数量:"<<endl;
cin>>n>>m;//n为点数,m为边数
//输出极点信息
cout<<"各个极点值挨次为:"<<endl;
for(i=0;i<n;i++)
{
fa[i]=i;
if(i!=0)
cout<<fa[i]<<"";
}
(完好word版)实验5最小生成树算法的设计与实现(报告)
(完好word版)实验5最小生成树算法的设计与实现(报告)
7/9
(完好word版)实验5最小生成树算法的设计与实现(报告)
cout<<endl;
cout<<"请输入边的信息(例子:145从极点1到极点4的边权为5)"<<
endl;
for(i=1;i<=m;i++)
cin>>e[i].fm>>e[i].to>>e[i].dist;//用边集数组存放边,方便排序和调用
sort(e+1,e+m+1,cmp);//对边按边权进行升序排序
intrst=n,ans=0;//rst表示目前的点共存在于多少个会集中,初始状况是每
个点都在不一样的会集中
for(i=1;i<=m&&rst>1;i++)
{
intx=e[i].fm,y=e[i].to;
if(same(x,y))continue;//same函数是盘问两个点能否在同一会集中
else
{
merge(x,y);//merge函数用来将两个点合并到同一会集中
rst--;//每次将两个不一样会集中的点合并,都将使rst值减1
ans+=e[i].dist;//这条边是最小生成树中的边,将答案加上面权
}
}
cout<<ans;
return0;
}
五、测试数据和相应的最小生成树
Input:
10
26
31
45
35
56
45
56
(完好word版)实验5最小生成树算法的设计与实现(报告)
(完好word版)实验5最小生成树算法的设计与实现(报告)
8/9
(完好word版)实验5最小生成树算法的设计与实现(报告)
364
462
566
Putout:
18
生成树为:
七、思虑题
1、微软面试题
一个大院子里住了50户人家,每家都养了一条狗,有一天他们接到通知说
院子里有狗生病了,并要求全部主人在发现自己家狗生病的当日就要把狗枪杀
掉。可是全部主人和他们的狗都不可以走开自己的房子,主人与主人之间也不可以
经过任何方式进行沟通,他们能做的不过经过窗户观察他人家的狗能否生病从而
判断自己的狗病否。(就是说,每个主人只好看出其余49家的狗是不是生病,
单独看自己的狗是看不出来的)第一天没有枪声,第二天还是没有枪声,第三天
(完好word版)实验5最小生成树算法的设计与实现(报告)
(完好word版)实验5最小生成树算法的设计与实现(报告)
9/9
(完好word版)实验5最小生成树算法的设计与实现(报告)
传出一阵枪声,问有多少条狗被枪杀。
(完好word版)实验5最小生成树算法的设计与实现(报告)
(完好word版)实验5最小生成树算法的设计与实现(报告)
9/9
(完好word版)实验5最小生成树算法的设计与实现(报告)
答:3只
假如只有一只病狗,那么当该病狗主人第一天发现其余49家都是好狗时就
会判断出自己家狗是病狗,那么第一天就会有枪声。
假如有两只病狗A和B,那么当两只狗主人对望时,看到了对方家里是病狗,那
么他们也不会判断出自己家狗狗能否生病,自然第一天第二天第三天以及今后都
不会有枪声。
假如有三只病狗A和B和C,那么其余47个主人都会看到3只病狗,而他们三
家却相互看到两只病狗,第一天没有枪声是由于ABC三家都看到了其余的病狗,
没有判断初自己家狗能否生病,第二天没有枪声则考据了A确立BC两家和他相同
也发现了两只病狗,同理BC也是。那么第三天ABC就会判断出自己家的狗是病
狗了。
提示:上面的大字
2、针对连通图初始边集最小堆表示,设计Kruskal算法。
详情请看文件实验五:
(完好word版)实验5最小生成树算法的设计与实现(报告)
(完好word版)实验5最小生成树算法的设计与实现(报告)
11/9
(完好word版)实验5最小生成树算法的设计与实现(报告)