Kruskal算法的设计和C实现.doc

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

1、实验三Kruskal算法的设计一、设计目的１.根据算法设计需要,掌握连通网的灵活表示方法;２.掌握最小生成树的Kruskal算法;３.基本掌握贪心算法的一般设计方法;４.进一步掌握集合的表示与操作算法的应用.二、设计内容1．主要数据类型与变量typedefstruct{intnum;inttag;}NODE;typedefstruct{intcost;intnode1;intnode2;}EDGE;NODEset[N];/*节点集*/EDGEes[N];/*边集*/EDGEst[N];/*最小生成树的边集*/2．算法或程序模块intF

2、ind(NODE*set,intelem)功能:在数组set中顺序查找元素elem,使用带压缩规则的查找算法,返回所在子集的根节点索引.intUnion(NODE*set,intelem1,intelem2)功能:应用Find算法首先找到elem1和elem2所在的子集,然后应用带加权规则的并运算算法合并两个子集.不成功时,返回-1;否则,返回并集的根节点索引.intInsertSort(EDGE*dat,intn)功能:用插入分类算法将连通图的边集按成本值的非降次序分类.intKruskal(EDGE*es,NODE*set,int

3、length,EDGE*st,intnum)功能:对有length条权值大于0的边,最小生成树中有num条边的连通图,应用Kruskal算法生成最小生成树,最小生成树的边存储在数组st中.voidOutput(EDGE*st,intn)功能:输出最小生成树的各条边.一、测试结果测试数据和结果1测试数据和结果2附：程序模块的源代码#include#include#defineN100intlength;typedefstruct{intnum;inttag;}NODE;typedefstruct{in

4、tcost;intnode1;intnode2;}EDGE;NODEset[N];/*节点集,n为连通网的节点数*/EDGEes[N];/*边集,m为连通网的边数*/EDGEst[N];/*最小生成树的边集*/intInsertSort(EDGE*dat,intn){inti,item,j,m,h;for(i=0;i

5、t[j].cost)&&(j>=0)){dat[j+1].cost=dat[j].cost;dat[j+1].node1=dat[j].node1;dat[j+1].node2=dat[j].node2;j--;}dat[j+1].cost=item;dat[j+1].node1=m;dat[j+1].node2=h;}}printf("权值排序结果(升序)：");for(i=0;i

6、inti,j,k;i=elem;while(set[i].tag>=0){i=set[i].tag;}j=elem;while(j!=i){k=set[j].tag;set[j].tag=i;j=k;}returni;}intUnion(NODE*set,intelem1,intelem2){intm,n,sum;m=Find(set,elem1);n=Find(set,elem2);sum=set[m].tag+set[n].tag;if(set[m].tag>set[n].tag){set[n].tag=sum;set[m].ta

7、g=n;}else{set[m].tag=sum;set[n].tag=m;}}intQuquanzhi(EDGE*es,intn){inti,j=0,len;EDGEb[N];for(i=0;i<=n;i++){if(es[i].cost>0){b[j].cost=es[i].cost;b[j].node1=es[i].node1;b[j].node2=es[i].node2;j++;}}len=j;printf("");for(i=0;i

8、i].node1;es[i].node2=b[i].node2;}printf("");returnlen;}intKruskal(EDGE*es,NODE*set,intlength,EDGE*st,intnum)