2022年实验5最小生成树算法的设计与实现 .pdf

《2022年实验5最小生成树算法的设计与实现 .pdf》由会员分享，可在线阅读，更多相关《2022年实验5最小生成树算法的设计与实现 .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、 5 2 3 5 3 4 5 2 5 6 1 2 6 3 5 6 5 6 6 1. 初始化时：属于最小生成树的顶点U= 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 9 页不属于最小生成树的顶点 V=1 ，2，3，4，5，6 2. 根据边权排序，选出还没有连接并且权最小的边（1 3 1），属于最小生成树的顶点 U=1，3 ，不属于最小生成树的顶点V=2,4,5,6 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 9 页3. 根据边权排序，选出还没有连接并且权最小的边（4 6 2

3、），属于最小生成树的顶点 U=1 ，3，4，6 （还没有合在一起，有两颗子树），不属于最小生成树的顶点 V=2,5 4. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点 U=1，3，4，6（合在一起），不属于最小生成树的顶点V=2,5 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 9 页5. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点 U=1，2，3，4，6, ，不属于最小生成树的顶点V=5 6. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成

4、树的顶点 U=1，2，3，4，5，6此时，最小生成树已完成精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 9 页四、实验程序的功能模块功能模块：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,cmp); /对边按边权进行升序排序详细代码：#include #include #in

5、clude #include #define MAXN_E 100000 #define MAXN_V 100000 using namespace std; struct Edge 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 9 页int fm,to,dist; /边的起始顶点，边的到达顶点，边权eMAXN_E; int faMAXN_V,n,m; /顶点数组，顶点总数，边总数/定义比较，只是边权比较bool cmp(Edge a,Edge b) return a.dist b.dist; /查找x的祖先int getfa(int

6、 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请输入顶点数目和边数目：nm;/n为点数， m为边数/输出顶点信息cout各个顶点值依次为： endl; for(i=0;in;

7、i+) fai=i; if(i!=0) coutfai ; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 9 页coutendl; cout请输入边的信息（例子： 1 4 5 从顶点 1到顶点 4的边权为 5）endl; for(i=1;iei.fmei.toei.dist;/ 用边集数组存放边， 方便排序和调用sort(e+1,e+m+1,cmp); /对边按边权进行升序排序int rst=n,ans=0;/rst 表示目前的点共存在于多少个集合中， 初始情况是每个点都在不同的集合中for(i=1;i1;i+) int x=ei.f

8、m,y=ei.to; if(same(x,y) continue;/same 函数是查询两个点是否在同一集合中else merge(x,y);/merge 函数用来将两个点合并到同一集合中rst-;/每次将两个不同集合中的点合并，都将使rst值减1 ans+=ei.dist;/这条边是最小生成树中的边，将答案加上边权 coutans; return 0; 五、测试数据和相应的最小生成树Input: 6 10 1 2 6 1 3 1 1 4 5 2 3 5 2 5 6 3 4 5 3 5 6 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共

9、 9 页3 6 4 4 6 2 5 6 6 Putout: 18生成树为：七、思考题1、微软面试题一个大院子里住了 50户人家，每家都养了一条狗，有一天他们接到通知说院子里有狗生病了，并要求所有主人在发现自己家狗生病的当天就要把狗枪杀掉。然而所有主人和他们的狗都不能够离开自己的房子，主人与主人之间也不能通过任何方式进行沟通， 他们能做的只是通过窗户观察别人家的狗是否生病从而判断自己的狗病否。（就是说，每个主人只能看出其他49家的狗是不是生病，单独看自己的狗是看不出来的）第一天没有枪声， 第二天还是没有枪声， 第三天传出一阵枪声，问有多少条狗被枪杀。精选学习资料 - - - - - - - -

10、- 名师归纳总结 - - - - - - -第 8 页，共 9 页答：3只假如只有一只病狗， 那么当该病狗主人第一天发现其他49家都是好狗时就会 判 断 出 自 己 家 狗 是 病 狗 ， 那 么 第 一 天 就 会 有 枪 声 。假如有两只病狗 A和B，那么当两只狗主人对望时，看到了对方家里是病狗，那么他们也不会判断出自己家狗狗是否生病，当然第一天第二天第三天以及以后都不会有枪声。假如有三只病狗 A和B和C，那么其他 47个主人都会看到 3只病狗，而他们三家却互相看到两只病狗，第一天没有枪声是因为ABC三家都看到了其他的病狗，没有判断初自己家狗是否生病， 第二天没有枪声则验证了A确定BC两家和他一样也发现了两只病狗，同理BC也是。那么第三天 ABC 就会判断出自己家的狗是病狗了。提示：上面的大字2、针对连通图初始边集最小堆表示，设计Kruskal算法。详情请看文件实验五：最小堆Kruskal.cpp 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 9 页