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

(完整word版)实验5最小生成树算法的设计与实现(报告)
(完整word版)实验5最小生成树算法的设计与实现(报告)
1/9
(完整word版)实验5最小生成树算法的设计与实现(报告)
实验5最小生成树算法的设计与实现
一、实验(完整word版)实验5最小生成树算法的设计与实现(报告)
(完整word版)实验5最小生成树算法的设计与实现(报告)
1/9
(完整word版)实验5最小生成树算法的设计与实现(报告)
实验5最小生成树算法的设计与实现
一、实验目的
1、根据算法设计需要,掌握连通图的灵活表示方法;
2、掌握最小生成树算法,如Prim、Kruskal算法;
3、基本掌握贪心算法的一般设计方法;
4、进一步掌握集合的表示与操作算法的应用。
二、实验内容
1、认真阅读算法设计教材和数据结构教材内容,熟习连通图的不同表示方
法和最小生成树算法;
2、设计Kruskal算法实验程序。
有n个城市可以用(n-1)条路将它们连通,求最小总路程的和。
设计测试问题,修改并调试程序,输出最小生成树的各条边,直至正确为止。
三、Kruskal算法的原理方法
边权排序:
131
462
364
145
235
345
256
126
356
566
:属于最小生成树的顶点 U={}
不属于最小生成树的顶点 V={1,2,3,4,5,6}
根据边权排序,选出还没有连接并且权最小的边(131),属于最小生成树的顶点U={1,3},不属于最小生成树的顶点V={2,4,5,6}
(完整word版)实验5最小生成树算法的设计与实现(报告)
(完整word版)实验5最小生成树算法的设计与实现(报告)
2/9
(完整word版)实验5最小生成树算法的设计与实现(报告)
根据边权排序,选出还没有连接并且权最小的边(462),属于最小生成树的顶点U={{1,3},{4,6}}(还没有合在一起,有两颗子树),不属于最小生成树的顶点V={2,5}
根据边权排序,选出还没有连接并且权最小的边(364),属于最小生成树的顶点U={1,3,4,6}(合在一起),不属于最小生成树的顶点V={2,5}
(完整word版)实验5最小生成树算法的设计与实现(报告)
(完整word版)实验5最小生成树算法的设计与实现(报告)
3/9
(完整word版)实验5最小生成树算法的设计与实现(报告)
根据边权排序,选出还没有连接并且权最小的边(364),属于最小生成树的顶点U={1,2,3,4,6},,不属于最小生成树的顶点V={5}
,选出还没有连接并且权最小的边( 364),属于最小生
(完整word版)实验5最小生成树算法的设计与实现(报告)
(完整word版)实验5最小生成树算法的设计与实现(报告)
4/9
(完整word版)实验5最小生成树算法的设计与实现(报告)
成树的顶点U={1,2,3,4,5,6}此时,最小生成树已完成
(完整word版)实验5最小生成树算法的设计与实现(报告)
(完整word版)实验5最小生成树算法的设计与实现(报告)
9/9
(完整word版)实验5最小生成树算法的设计与实现(报告)
四、实验程序的功能模块
功能模块:
bo