实验5最小生成树算法的设计与实现(报告)

1、实验5 最小生成树算法的设计与实现1、 实验目的1、根据算法设计需要, 掌握连通图的灵活表示方法；2、掌握最小生成树算法，如Prim、Kruskal算法；3、基本掌握贪心算法的一般设计方法；4、进一步掌握集合的表示与操作算法的应用。2、 实验内容1、认真阅读算法设计教材和数据结构教材内容, 熟习连通图的不同表示方法和最小生成树算法；2、设计Kruskal算法实验程序。有n个城市可以用（n-1）条路将它们连通，求最小总路程的和。设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止。3、 Kruskal算法的原理方法边权排序:1 3 14 6 23 6 41 4 52 3 53

2、4 52 5 61 2 63 5 65 6 61. 初始化时：属于最小生成树的顶点U=不属于最小生成树的顶点V=1，2，3，4，5，62. 根据边权排序，选出还没有连接并且权最小的边（1 3 1），属于最小生成树的顶点U=1，3，不属于最小生成树的顶点V=2,4,5,63. 根据边权排序，选出还没有连接并且权最小的边（4 6 2），属于最小生成树的顶点U=1，3，4，6（还没有合在一起，有两颗子树），不属于最小生成树的顶点V=2,54. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U=1，3，4，6（合在一起），不属于最小生成树的顶点V=2,55. 根据边权排

3、序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U=1，2，3，4，6,，不属于最小生成树的顶点V=56. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U=1，2，3，4，5，6此时，最小生成树已完成4、 实验程序的功能模块功能模块：bool cmp(Edge a,Edge b)； /定义比较方法int getfa(int x)；/在并查集森林中找到x的祖先int same(int x,int y)； /判断祖先是否是同一个，即是否联通void merge(int x,int y); /合并子树，即联通两子树sort(e+1,e+m+1,c

4、mp); /对边按边权进行升序排序详细代码：#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define MAXN_E 100000#define MAXN_V 100000using namespace std;struct Edge int fm,to,dist; /边的起始顶点，边的到达顶点，边权eMAXN_E;int faMAXN_V,n,m; /顶点数组，顶点总数，边总数/定义比较，只是边权比较bool cmp(Edge a,Edge

5、b) return a.dist < b.dist;/查找x的祖先int getfa(int x)/getfa是在并查集森林中找到x的祖先 if(fax=x) return fax; else return fax = getfa(fax);/判断祖先是否是同一个，即是否联通int same(int x,int y) return getfa(x)=getfa(y);/合并两棵树void merge(int x,int y) int fax=getfa(x),fay=getfa(y); fafax=fay;int main()int i;cout<<"请输入顶点数目

6、和边数目："<<endl; cin>>n>>m;/n为点数，m为边数/输出顶点信息cout<<"各个顶点值依次为："<<endl;for(i=0;i<n;i+)fai=i;if(i!=0)cout<<fai<<" "cout<<endl;cout<<"请输入边的信息（例子：1 4 5 从顶点1到顶点4的边权为5）"<<endl; for(i=1;i<=m;i+)cin>>ei.fm&

7、gt;>ei.to>>ei.dist;/用边集数组存放边，方便排序和调用sort(e+1,e+m+1,cmp); /对边按边权进行升序排序 int rst=n,ans=0;/rst表示目前的点共存在于多少个集合中，初始情况是每个点都在不同的集合中 for(i=1;i<=m && rst>1;i+) int x=ei.fm,y=ei.to; if(same(x,y) continue;/same函数是查询两个点是否在同一集合中 else merge(x,y);/merge函数用来将两个点合并到同一集合中 rst-;/每次将两个不同集合中的点合并，都将

8、使rst值减1 ans+=ei.dist;/这条边是最小生成树中的边，将答案加上边权 cout<<ans; return 0;5、 测试数据和相应的最小生成树Input:6 101 2 61 3 11 4 52 3 52 5 63 4 53 5 63 6 44 6 25 6 6Putout:18生成树为：七、思考题1、微软面试题一个大院子里住了50户人家，每家都养了一条狗，有一天他们接到通知说院子里有狗生病了，并要求所有主人在发现自己家狗生病的当天就要把狗枪杀掉。然而所有主人和他们的狗都不能够离开自己的房子，主人与主人之间也不能通过任何方式进行沟通，他们能做的只是通过窗户观察别人家

9、的狗是否生病从而判断自己的狗病否。（就是说，每个主人只能看出其他 49家的狗是不是生病，单独看自己的狗是看不出来的）第一天没有枪声，第二天还是没有枪声，第三天传出一阵枪声，问有多少条狗被枪杀。答：3只 假如只有一只病狗，那么当该病狗主人第一天发现其他49家都是好狗时就会判断出自己家狗是病狗，那么第一天就会有枪声。假如有两只病狗A和B，那么当两只狗主人对望时，看到了对方家里是病狗，那么他们也不会判断出自己家狗狗是否生病，当然第一天第二天第三天以及以后都不会有枪声。假如有三只病狗A和B和C，那么其他47个主人都会看到3只病狗，而他们三家却互相看到两只病狗，第一天没有枪声是因为ABC三家都看到了其他的病狗，没有判断初自己家狗是否