2022年实验最小生成树算法的设计与实现.docx
精选学习资料 - - - - - - - - - 试验 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 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）,属于最小生成树的顶点 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）,属于最小生成树的顶点 U=1 ,2,3,4,5,6 此时,最小生成树已完成名师归纳总结 - - - - - - -第 4 页,共 9 页精选学习资料 - - - - - - - - - 四、试验程序的功能模块功能模块：bool cmpEdge a,Edge b； /定义比较方法int getfaint x；/在并查集森林中找到 x 的祖先int sameint x,int y；/判定祖先是否是同一个,即是否联通void mergeint x,int y; /合并子树,即联通两子树sorte+1,e+m+1,cmp; 具体代码：#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> /对边按边权进行升序排序#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 cmpEdge a,Edge b return a.dist < b.dist; /查找x的祖先int getfaint x/getfa 是在并查集森林中找到 x的祖先iffax=x return fax; else return fax = getfafax; /判定祖先是否是同一个,即是否联通int sameint x,int y return getfax=getfay; /合并两棵树void mergeint x,int y int fax=getfax,fay=getfay; fafax=fay; int main int i; cout<<"请输入顶点数目和边数目："<<endl; cin>>n>>m;/n为点数, m为边数/输出顶点信息cout<<"各个顶点值依次为： "<<endl; fori=0;i<n;i+ fai=i; ifi.=0 cout<<fai<<" " 名师归纳总结 - - - - - - -第 6 页,共 9 页精选学习资料 - - - - - - - - - cout<<endl; cout<<"请输入边的信息（例子： 1 4 5 从顶点 1到顶点 4的边权为 5）"<< endl; fori=1;i<=m;i+ cin>>ei.fm>>ei.to>>ei.dist;/ 用边集数组存放边, 便利排序和调用sorte+1,e+m+1,cmp; /对边按边权进行升序排序int rst=n,ans=0;/rst表示目前的点共存在于多少个集合中, 初始情形是每个点都在不同的集合中fori=1;i<=m && rst>1;i+ int x=ei.fm,y=ei.to; ifsamex,y continue;/same函数是查询两个点是否在同一集合中else mergex,y;/merge函数用来将两个点合并到同一集合中rst-;/每次将两个不同集合中的点合并,都将使 rst值减 1 ans+=ei.dist;/这条边是最小生成树中的边,将答案加上边权 cout<<ans; 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 页精选学习资料 - - - - - - - - - 3 6 4 4 6 2 5 6 6 Putout: 18生成树为：七、摸索题1、微软面试题一个大院子里住了 50 户人家,每家都养了一条狗,有一天他们接到通知说院子里有狗生病了,并要求全部主人在发觉自己家狗生病的当天就要把狗枪杀掉；然而全部主人和他们的狗都不能够离开自己的房子,主人与主人之间也不能通过任何方式进行沟通, 他们能做的只是通过窗户观看别人家的狗是否生病从而判定自己的狗病否；（就是说,每个主人只能看出其他49 家的狗是不是生病,单独看自己的狗是看不出来的）第一天没有枪声, 其次天仍是没有枪声, 第三天传出一阵枪声,问有多少条狗被枪杀；名师归纳总结 - - - - - - -第 8 页,共 9 页精选学习资料 - - - - - - - - - 答： 3只假如只有一只病狗, 那么当该病狗主人第一天发觉其他 49家都是好狗时就会 判 断 出 自 己 家 狗 是 病 狗 , 那 么 第 一 天 就 会 有 枪 声 ；假如有两只病狗 A 和B,那么当两只狗主人对望时,看到了对方家里是病狗,那么他们也不会判定出自己家狗狗是否生病,不会有枪声；当然第一天其次天第三天以及以后都假如有三只病狗 A和B和C,那么其他 47个主人都会看到 3只病狗,而他们三家却相互看到两只病狗,第一天没有枪声是由于ABC 三家都看到了其他的病狗,没有判定初自己家狗是否生病, 其次天没有枪声就验证了 A确定 BC两家和他一样也发觉了两只病狗,同理 狗了；提示：上面的大字BC也是；那么第三天 ABC 就会判定出自己家的狗是病名师归纳总结 2、针对连通图初始边集最小堆表示,设计Kruskal算法；第 9 页,共 9 页详情请看文件试验五：最小堆Kruskal.cpp - - - - - - -
