实验--Kruskal算法的设计

实验四Kruskal算法的设计[实验目的]１.根据算法设计需要,掌握连通网的灵活表示方法;２.掌握最小生成树的Kruskal算法;３.基本掌握贪心算法的一般设计方法;４.进一步掌握集合的表示与操作算法的应用.[预习要求]１.认真阅读算法设计教材和数据结构教材内容,熟习连通网的不同表示方法和最小生成树算法;２.设计Kruskal算法实验程序#includestdio.h#defineN20intV=0;inta[100];intE;typedefstructdat{intvs;intve;intweight;}DATA;DATAdata[20];intfind(inti){if(a[i]==i)returna[i];elsereturnfind(a[i]);}voidsort(){inti,j;for(i=0;iV;i++)for(j=0;jV-1;j++){if(data[j].weightdata[j+1].weight){DATAt;t=data[j];data[j]=data[j+1];data[j+1]=t;}}}intKU(){inti,x,y,j=0;;intsum=0;for(i=0;iV;i++)a[i]=i;for(i=0;iV;i++){x=find(data[i].vs);y=find(data[i].ve);if(x!=y){sum=sum+data[i].weight;a[x]=y;j++;}if(j==E-1)break;}returnsum;}voidmain(){intsum=0;ints,e,w;inti=0;scanf(%d,&E);while(scanf(%d%d%d,&s,&e,&w)!=EOF){if(s==0&&e==0&&w==0)break;data[i].vs=s;data[i].ve=e;data[i].weight=w;i++;V++;}sort();sum=KU();printf(%d\n,sum);}.[实验步骤]1.设计测试问题,修改并调试程序,输出最小生成树的各条边,直至正确为止;2.待各功能子程序调试完毕,去掉测试程序,将你的程序整理成功能模块存盘备用.[实验报告要求]1.阐述实验目的和实验内容;2.阐述Kruskal算法的原理方法;3.提交实验程序的功能模块;4.提供测试数据和相应的最小生成树.[思考与练习]1.设计由连通网初始边集数组生成最小堆的算法;2.设计输出堆顶元素,并将剩余元素调整成最小堆的算法;3.针对连通网初始边集最小堆表示,设计Kruskal算法;4.采用成本邻接矩阵表示连通网时,在剩余边中如何实现最小成本边的查找?采用成本邻接矩阵表示连通网时,用C语言实现Prim算法.