Kruskal算法的设计和C实现

实验三Kruskal算法的设计一、设计目的1.根据算法设计需要，掌握连通网的灵活表示方法；.掌握最小生成树的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算法首先找到elemi和elem2所在的子集，然后应用带加权规则的并运算算法合并两个子集.不成功时,返回-1；否则,返回并集的根节点索引.intInsertSort(EDGE*dat,intn)功能：用插入分类算法将连通图的边集按成本值的非降次序分类.intKruskal(EDGE*es,NODE*set,intlength,EDGE*st,intnum)功能：对有length条权值大于0的边，最小生成树中有num条边的连通图，应用Kruskal算法生成最小生成树，最小生成树的边存储在数组st中.voidOutput(EDGE*st,intn)

功能：输出最小生成树的各条边.三测试结果 、测试数据和结果1C:\llsers\wxz\Deslb:op\5hiyan»ese碁不相邻则输入T=4<—>6=205<—>6-55当主it也山边也山边也山边也勺也也力边.■TL.11K. ;「：-「J. I.■.■-1■.1-1.■.1IT—.—-1.■.11.-■Ti.1C:\Users\wxz\Deslctop\5hiyan.ese权恒排序結果l升序》:10IE20 25 30 35 40 45 50 55最小权值边和:nincost=185聂小树的边数；5最小生成树的为：1234512345树的表示：set[01.rum=lset[11树的表示：set[01.rum=lset[11.rum=2set[21=rmm=3se七[3]■riurn^4setL41.rum=5settS1.ru,m=6setL0Ktag=2set[1]-tag=0set[2J=ta«j=—6:st：七[3]-tagr-2set14J.tag=Zset[5J.tag=2测试数据和结果2回回IfC:\Users\wxz\Desktop\shiy3n.eie诗触人结点彳冲羅人边的权值，若不碗输入-1边：K—>2=15远K—>3=20远K—>4=7ffi；K—>5=-1迅2<—>3=-1陋:2<—>4=28迅:2<—>5=3远3<—>4=30远3<—>5=-1远4<—>5=8.附：程序模块的源代码#include<stdio.h>#include<conio.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;i<n;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((item<dat[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;i<n;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].tag>set[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].cost>0){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;i<len;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;i<length;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;i<n;i++){printf("边％4:%3dv-->%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；i<length；i++){set[i].num=i；set[i].tag=-1；}printf("请输入边的权值，若不相邻则输入-1\n");for(i=0；i<length；i++){for(j=i+1;j<length;j++){ printf("边：％dv-->%d=",i+1j+1);scanf("%d",&es[k].cost);es[k].node1=i;es[k].node2=j;k++;}}temp=k;L=Ququanzhi(es,temp);/*提出权值大于0的边数*/InsertSort(