最小生成树算法的设计与实现
一、实验目的
1、根据算法设计需要掌握连通网的灵活表示方法2、掌握最小生成树算法，如Prim、Kruskal算法3、基本掌握贪心算法的一般设计方法4、进一步掌握集合的表示与操作算法的应用
二、预习与参考
1、认真阅读算法设计教材和数据结构教材内容熟习连通网的不同表示方法和最小生成树算法2、设计Kruskal算法实验程序参考数据类型或变量typedefNodeNumberi
t节点编号typedefCostTypei
t成本值类型
typedefElemTypeNodeNumber实型或任意其它元素类型typedefstructi
tElemTypei
ttagNODEtypedefstructCostTypecostNodeNumber
ode1
ode2EDGENODEset11…
1节点集
为连通网的节点数
EDGEesvaluesofe1…valuesofem边集m为连通网的边数EDGEst
1最小生成树的边集参考子程序接口与功能描述i
tFi
dNODEsetElemTypeelem功能在数组set中顺序查找元素elem如果不成功返回1否则使用带压缩规则的查找算法返回所在子集的根节点索引i
tU
io
NODEsetElemTypeelem1ElemTypeelem2功能应用Fi
d算法首先找到elem1和elem2所在的子集然后应用带加权规则的并运算算法合并两个子集不成功时返回1否则返回并集的根节点索引voidSortEDGEesi
t

f功能用任意分类算法将连通图的边集按成本值的非降次序分类voidKruskalEDGEesi
tmNODEseti
t
EDGEst功能对有
个节点m条边的连通网应用Kruskal算法生成最小生成树最小生成树的边存储在数组st中voidOutputEDGEsti
t
功能输出最小生成树的各条边
三、实验要求
上机实验时，一人一组，独立上机。有
个城市可以用（
1）条路将它们连通，求最小总路程的和。
四、实验步骤
1、设计测试问题修改并调试程序输出最小生成树的各条边直至正确为止2、待各功能子程序调试完毕去掉测试程序将你的程序整理成功能模块存盘备用
五、测试
I
put6126131145235256345356364462566000Putout18
六、实验报告要求
1、阐述实验目的和实验内容2、阐述Kruskal算法的原理方法3、提交实验程序的功能模块
f4、提供测试数据和相应的最小生成树。
七、思考题
1、设计由连通网初始边集数组生成最小堆的算法2、设计输出堆顶元素并将剩余元素调整成最小堆的算法3、针对连通网初始边集最小堆表示设计Kruskal算法4、采用成本邻接矩阵表示连通网时在剩余边中如何实现最小成本边的查找采用成本邻接矩阵表示连通网时用C语言实现Prim算法
fr