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

1、（完整word版）实验5最小生成树算法的设计与实现（报告）编辑整理:尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对 文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（完整word版）实验5最小生 成树算法的设计与实现（报告）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您 的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改,如果觉得对您有帮助请收藏以便随时查阅,最后祝您生活愉快业绩进步,以 下为（完整word版）实验5最小生成树算法的设计与实现（报告）的全部内容。卖脍5最小生成树算廉的役计与卖现一、实验

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

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

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

5、ncIude cstdio#incIudecstring# i ncIude #define MAXN_E 100000#define MAXN_V 100000us i ng namespace std;struet Edge int fm, to, dist；/边的起始顶点，边的到达顶点，边权)eMAXN_E；int fa MAXN_V , n, m;/顶点数组，顶点总数，边总数/定义比较,只是边权比较boo I cmp (Edgea,Edge b) return aodistb.dist;/查找x的祖先int getfa (int x) /getfa是在并查集森林中找到x的祖先if(fa

6、x=x) return fa x；e I se return fax = getfa (fa x);/判断祖先是否是同一个，即是否联通int same (int x, int y) return getfa(x) =getfa(y);)/合并两棵树void merge (int x, int y) int fax二getfa (x) , fay=getfa (y);fa fax=fay；int main () int i;cout”请输入顶点数目和边数目： n m； /n为点数，m为边数/输出顶点信息coutJ,各个顶点值依次为:nendl;for (i=0； i ei. fm e i. to

7、 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=e i。fm, y=e i oto;if (same (x, y) cont i nue;/same函数是查询两个点是否在同一集合 中e I semerge (x, y) ； /merge函数用来将两个点合并到同一集合中rst；/每次将两个不同集合中的点合并，都将使rst值减1an

8、s+二ei。dist；/这条边是最小生成树中的边，将答案加上边 权coutans;return 0；五、测试数据和相应的最小生成树Input:611122333452343545666106155656426F:算法设计与分析傑验5Debuglcnjslc3l.exe”343545666223334518Press arniy key to continuePutou18生成树为:七、思考题1、微软面试题一个大院子里住了50户人家， 每家都养了一条狗， 有一天他们接到通知说院子里 有狗生病了，并要求所有主人在发现自己家狗生病的当天就要把狗枪杀掉然而所有 主人和他们的狗都不能够离开自己的房子，主

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