算法设计之Kruskal算法的设计

实验三Kruskal算法的设计[实验目的]１.根据算法设计需要,掌握连通网的灵活表示方法;２.掌握最小生成树的Kruskal算法;３.基本掌握贪心算法的一般设计方法;４.进一步掌握集合的表示与操作算法的应用.[预习要求]１.认真阅读算法设计教材和数据结构教材内容,熟习连通网的不同表示方法和最小生成树算法;２.设计Kruskal算法实验程序.[参考数据类型或变量]typedefNodeNumberint;/*节点编号*/typedefCostTypeint;/*成本值类型*/typedefElemTypeNodeNumber/*实型或任意其它元素类型*/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中顺序查找元素elem,如果不成功,返回-1;否则,使用带压缩规则的查找算法,返回所在子集的根节点索引.intUnion(NODE*set,ElemTypeelem1,ElemTypeelem2)功能:应用Find算法首先找到elem1和elem2所在的子集,然后应用带加权规则的并运算算法合并两个子集.不成功时,返回-1;否则,返回并集的根节点索引.voidSort(EDGE*es,intn)功能:用任意分类算法将连通图的边集按成本值的非降次序分类.voidKruskal(EDGE*es,intm,NODE*set,intn,EDGE*st)功能:对有n个节点,m条边的连通网,应用Kruskal算法生成最小生成树,最小生成树的边存储在数组st中.voidOutput(EDGE*st,intn)功能:输出最小生成树的各条边.[实验步骤]1.设计测试问题,修改并调试程序,输出最小生成树的各条边,直至正确为止;2.待各功能子程序调试完毕,去掉测试程序,将你的程序整理成功能模块存盘备用.[实验报告要求]1.阐述实验目的和实验内容;2.阐述Kruskal算法的原理方法;3.提交实验程序的功能模块;4.提供测试数据和相应的最小生成树.[思考与练习]1.设计由连通网初始边集数组生成最小堆的算法;2.设计输出堆顶元素,并将剩余元素调整成最小堆的算法;3.针对连通网初始边集最小堆表示,设计Kruskal算法;4.采用成本邻接矩阵表示连通网时,在剩余边中如何实现最小成本边的查找?采用成本邻接矩阵表示连通网时,用C语言实现Prim算法.Kruskal算法：#includeiostream#includestring#includealgorithmusingnamespacestd;typedefstructnode//边结构{intu;//边的起点intv;//边的终点intdist;//边的长度}node;nodeedge[10000];//定义一万条边intn;//n表示程序中边的总数intuse[10000];//该数组用于标记某条边是否被选入最小生成树intpre[10000];//定义一个并查集数组voidinit_pre()//初始化并查集数组{inti;for(i=0;in;i++)pre[i]=i;}intfind(intx)//查找x元素所属集合的根{intr=x;while(pre[r]!=r){r=pre[r];}returnr;}voidUnion(inta,intb)//合并a,b两元素到一个集合{pre[a]=b;}voidKruskal(){inti,f1,f2,sumdist=0;for(i=0;in;i++){use[i]=0;//等于0表示第i条边未被选入最小生成树}init_pre();//初始化并查集for(i=0;in;i++){f1=find(edge[i].u);//检查第i边的起点和终点是否在一个集合，不是的话就合并f2=find(edge[i].v);if(f1!=f2){Union(f1,f2);use[i]=1;//标记改为选用sumdist+=edge[i].dist;}}printf(Thesumdistofthetreeis:%d\n,sumdist);printf(Thetreeare:\n);for(i=0;in;i++){if(use[i])printf(%d%d\n,edge[i].u,edge[i].v);}}intmain(){inti,j,k,m;printf(Pleaseinputhowmanynodesandedges:\n);scanf(%d%d,&m,&n);//m个结点，n条边printf(Pleaseinput%dedge'sbeginnode,endnodeanddist:\n,n);for(i=0;in;i++){scanf(%d%d%d,&edge[i].u,&edge[i].v,&edge[i].dist);//输入n条边的起点终点和长度}for(i=0;in;i++)//用冒泡排序将所有边按长度从小到大排序{k=i;for(j=i;jn;j++){if(edge[j].distedge[k].dist)k=j;}swap(edge[i],edge[k]);}Kruskal();return0;}