电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

完整版试验5最小生成树算法的设计与实现报告VIP免费

完整版试验5最小生成树算法的设计与实现报告_第1页
1/9
完整版试验5最小生成树算法的设计与实现报告_第2页
2/9
完整版试验5最小生成树算法的设计与实现报告_第3页
3/9
实验 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={} 不属于最小生成树的顶点 V={1 ,2,3,4,5,6} 2. 根据边权排序,选出还没有连接并且权最小的边(1 3 1),属于最小生成树的顶点 U={1 ,3} ,不属于最小生成树的顶点V={2,4,5,6} 3. 根据边权排序,选出还没有连接并且权最小的边(4 6 2),属于最小生成树的顶点 U={{1 ,3} ,{4 ,6}} (还没有合在一起,有两颗子树),不属于最小生成树的顶点 V={2,5} 4. 根据边权排序,选出还没有连接并且权最小的边(3 6 4),属于最小生成树的顶点 U={1 ,3,4,6} (合在一起),不属于最小生成树的顶点V={2,5} 5. 根据边权排序,选出还没有连接并且权最小的边(3 6 4),属于最小生成树的顶点 U={1 ,2,3,4,6}, ,不属于最小生成树的顶点V={5} 6. 根据边权排序,选出还没有连接并且权最小的边(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(int x,int y); //合并子树,即联通两子树sort(e+1,e+m+1,cmp); //对边按边权进行升序排序详细代码:#include #include #include #include #define MAXN_E 100000 #define MAXN_V 100000 using namespace std; struct Edge{ int fm,to,dist; //边的起始顶点,边的到达顶点,边权}e[MAXN_E]; int fa[MAXN_V],n,m; //顶点数组,顶点总数,边总数//定义比较,...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

完整版试验5最小生成树算法的设计与实现报告

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部