算法设计之Kruskal算法的设计.doc

《算法设计之Kruskal算法的设计.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验三Kruskal算法的设计[实验目的]１.根据算法设计需要,掌握连通网的灵活表示方法;２.掌握最小生成树的Kruskal算法;３.基本掌握贪心算法的一般设计方法;４.进一步掌握集合的表示与操作算法的应用.[预习要求]１.认真阅读算法设计教材和数据结构教材内容,熟习连通网的不同表示方法和最小生成树算法;２.设计Kruskal算法实验程序.[参考数据类型或变量]typedefNodeNumberint;/*节点编号*/typedefCostTypeint;/*成本值类型*/typedefElemTypeNodeNumber/*实型或任意其它元素类

2、型*/typedefstruct{intElemType;inttag;}NODE;typedefstruct{CostTypecost;NodeNumbernode1,node2;}EDGE;NODEset[]={{1,-1},…,{n,-1}};/*节点集,n为连通网的节点数*/EDGEes[]={{valuesofe1},…,{valuesofem}};/*边集,m为连通网的边数*/EDGEst[n-1];/*最小生成树的边集*/[参考子程序接口与功能描述]intFind(NODE*set,ElemTypeelem)功能:在数组set中顺序

3、查找元素elem,如果不成功,返回-1;否则,使用带压缩规则的查找算法,返回所在子集的根节点索引.intUnion(NODE*set,ElemTypeelem1,ElemTypeelem2)功能:应用Find算法首先找到elem1和elem2所在的子集,然后应用带加权规则的并运算算法合并两个子集.不成功时,返回-1;否则,返回并集的根节点索引.voidSort(EDGE*es,intn)功能:用任意分类算法将连通图的边集按成本值的非降次序分类.voidKruskal(EDGE*es,intm,NODE*set,intn,EDGE*st)功能:对有

4、n个节点,m条边的连通网,应用Kruskal算法生成最小生成树,最小生成树的边存储在数组st中.voidOutput(EDGE*st,intn)功能:输出最小生成树的各条边.[实验步骤]1.设计测试问题,修改并调试程序,输出最小生成树的各条边,直至正确为止;2.待各功能子程序调试完毕,去掉测试程序,将你的程序整理成功能模块存盘备用.[实验报告要求]1.阐述实验目的和实验内容;2.阐述Kruskal算法的原理方法;3.提交实验程序的功能模块;4.提供测试数据和相应的最小生成树.[思考与练习]1.设计由连通网初始边集数组生成最小堆的算法;2.设计输出

5、堆顶元素,并将剩余元素调整成最小堆的算法;3.针对连通网初始边集最小堆表示,设计Kruskal算法;4.采用成本邻接矩阵表示连通网时,在剩余边中如何实现最小成本边的查找?采用成本邻接矩阵表示连通网时,用C语言实现Prim算法.Kruskal算法：#include#include#includeusingnamespacestd;typedefstructnode//边结构{intu;//边的起点intv;//边的终点intdist;//边的长度}node;nodeedge[10000];/

6、/定义一万条边intn;//n表示程序中边的总数intuse[10000];//该数组用于标记某条边是否被选入最小生成树intpre[10000];//定义一个并查集数组voidinit_pre()//初始化并查集数组{inti;for(i=0;i

7、f1,f2,sumdist=0;for(i=0;i

8、rintf("Thetreeare:");for(i=0;i