Kruskal算法的设计和C实现

实验三Kruskal算法的设计一、设计目的１.根据算法设计需要,掌握连通网的灵活表示方法;２.掌握最小生成树的Kruskal算法;３.基本掌握贪心算法的一般设计方法;４.进一步掌握集合的表示与操作算法的应用.二、设计内容1．主要数据类型与变量typedefstruct{intnum;inttag;}NODE;typedefstruct{intcost;intnode1;intnode2;}EDGE;NODEset[N];/*节点集*/EDGEes[N];/*边集*/EDGEst[N];/*最小生成树的边集*/2．算法或程序模块intFind(NODE*set,intelem)功能:在数组set中顺序查找元素elem,使用带压缩规则的查找算法,返回所在子集的根节点索引.intUnion(NODE*set,intelem1,intelem2)功能:应用Find算法首先找到elem1和elem2所在的子集,然后应用带加权规则的并运算算法合并两个子集.不成功时,返回-1;否则,返回并集的根节点索引.intInsertSort(EDGE*dat,intn)功能:用插入分类算法将连通图的边集按成本值的非降次序分类.intKruskal(EDGE*es,NODE*set,intlength,EDGE*st,intnum)功能:对有length条权值大于0的边,最小生成树中有num条边的连通图,应用Kruskal算法生成最小生成树,最小生成树的边存储在数组st中.voidOutput(EDGE*st,intn)功能:输出最小生成树的各条边.三、测试结果测试数据和结果1测试数据和结果2附：程序模块的源代码#includestdio.h#includeconio.h#defineN100intlength;typedefstruct{intnum;inttag;}NODE;typedefstruct{intcost;intnode1;intnode2;}EDGE;NODEset[N];/*节点集,n为连通网的节点数*/EDGEes[N];/*边集,m为连通网的边数*/EDGEst[N];/*最小生成树的边集*/intInsertSort(EDGE*dat,intn){inti,item,j,m,h;for(i=0;in;i++){item=dat[i].cost;m=dat[i].node1;h=dat[i].node2;if(i==0){j=0;dat[j].cost=item;}else{j=i-1;while((itemdat[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(权值排序结果(升序)：\n);for(i=0;in;i++)printf(%4d,dat[i].cost);printf(\n\n);}intFind(NODE*set,intelem){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].tagset[n].tag){set[n].tag=sum;set[m].tag=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].cost0){b[j].cost=es[i].cost;b[j].node1=es[i].node1;b[j].node2=es[i].node2;j++;}}len=j;printf(\n);for(i=0;ilen;i++){es[i].cost=b[i].cost;es[i].node1=b[i].node1;es[i].node2=b[i].node2;}printf(\n);returnlen;}intKruskal(EDGE*es,NODE*set,intlength,EDGE*st,intnum){inti,j,k=1,m,n,mincost=0;st[0].cost=es[0].cost;st[0].node1=es[0].node1;st[0].node2=es[0].node2;m=Find(set,st[0].node1);n=Find(set,st[0].node2);Union(set,m,n);mincost+=es[0].cost;for(i=1;ilength;i++)/*找其他边*/{m=Find(set,es[i].node1);n=Find(set,es[i].node2);if(m!=n){Union(set,m,n);st[k].cost=es[i].cost;st[k].node1=es[i].node1;st[k].node2=es[i].node2;mincost+=es[i].cost;k++;}if(k==num)break;}printf(\n最小权值边和：mincost=%d\n,mincost);printf(\n最小树的边数：%d\n\n,k);returnk;}voidOutput(EDGE*st,intn){inti;printf(最小生成树的为：\n\n);for(i=0;in;i++){printf(树边%d:%3d--%d=%d\n,i+1,st[i].node1+1,st[i].node2+1,st[i].cost);}}intmain(){inti,j,k=0,L,temp,len;NODE*p,*q;textbackground(BLUE);textcolor(YELLOW);system(graftabl935);/*显示中文必须的代码*/clrscr();printf(请输入结点个数：);scanf(%d,&length);for(i=0;ilength;i++){set[i].num=i;set[i].tag=-1;}printf(请输入边的权值，若不相邻则输入-1\n);for(i=0;ilength;i++){for(j=i+1;jlength;j++){printf(边：%d--%d=,i+1,j+1);scanf(%d,&es[k].cost);es[k].node1=i;es[k].node2=j;k++;}}temp=k;L=Ququanzhi(es,temp);/*提出权值大于0的边数*/InsertSort(es,L);/*将权值递增排列*/printf(\n);len=Kruskal(es,set,L,st,length-1);Output(st,len);printf(\n树的表示：\n);for(i=0;ilength;i++)printf(set[%d].num=%dset[%d].tag=%d\n,i,set[i].num+1,i,set[i].tag);getch();}