Kruskal算法的設(shè)計和C實現(xiàn)

實驗三Kruskal算法的設(shè)計一、設(shè)計目的1.根據(jù)算法設(shè)計需要，掌握連通網(wǎng)的靈活表示方法；.掌握最小生成樹的Kruskal算法；.基本掌握貪心算法的一般設(shè)計方法；.進(jìn)一步掌握集合的表示與操作算法的應(yīng)用.二、設(shè)計內(nèi)容1．主要數(shù)據(jù)類型與變量typedefstruct{intnum;inttag;}NODE;typedefstruct{intcost;intnode1;intnode2;}EDGE;NODEset[N];/*節(jié)點集*/EDGEes[N];/*邊集*/EDGEst[N];/*最小生成樹的邊集*/2．算法或程序模塊intFind(NODE*set,intelem)功能：在數(shù)組set中順序查找元素elem,使用帶壓縮規(guī)則的查找算法，返回所在子集的根節(jié)點索引.intUnion(NODE*set,intelem1,intelem2)功能：應(yīng)用Find算法首先找到elemi和elem2所在的子集，然后應(yīng)用帶加權(quán)規(guī)則的并運算算法合并兩個子集.不成功時,返回-1；否則,返回并集的根節(jié)點索引.intInsertSort(EDGE*dat,intn)功能：用插入分類算法將連通圖的邊集按成本值的非降次序分類.intKruskal(EDGE*es,NODE*set,intlength,EDGE*st,intnum)功能：對有l(wèi)ength條權(quán)值大于0的邊，最小生成樹中有num條邊的連通圖，應(yīng)用Kruskal算法生成最小生成樹，最小生成樹的邊存儲在數(shù)組st中.voidOutput(EDGE*st,intn)

功能：輸出最小生成樹的各條邊.三測試結(jié)果 、測試數(shù)據(jù)和結(jié)果1C:\llsers\wxz\Deslb:op\5hiyan?ese碁不相鄰則輸入T=4<—>6=205<—>6-55當(dāng)主it也山邊也山邊也山邊也勺也也力邊.■TL.11K. ;「：-「J. I.■.■-1■.1-1.■.1IT—.—-1.■.11.-■Ti.1C:\Users\wxz\Deslctop\5hiyan.ese權(quán)恒排序結(jié)果l升序》:10IE20 25 30 35 40 45 50 55最小權(quán)值邊和:nincost=185聶小樹的邊數(shù)；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測試數(shù)據(jù)和結(jié)果2回回IfC:\Users\wxz\Desktop\shiy3n.eie詩觸人結(jié)點彳沖羅人邊的權(quán)值，若不碗輸入-1邊：K—>2=15遠(yuǎn)K—>3=20遠(yuǎn)K—>4=7ffi；K—>5=-1迅2<—>3=-1陋:2<—>4=28迅:2<—>5=3遠(yuǎn)3<—>4=30遠(yuǎn)3<—>5=-1遠(yuǎn)4<—>5=8.附：程序模塊的源代碼#include<stdio.h>#include<conio.h>#defineN100intlength;typedefstruct{intnum;inttag;}NODE;typedefstruct{intcost;intnode1;intnode2;}EDGE;NODEset[N];/*節(jié)點集,n為連通網(wǎng)的節(jié)點數(shù)*/EDGEes[N];/*邊集,m為連通網(wǎng)的邊數(shù)*/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("權(quán)值排序結(jié)果(升序)：\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最小權(quán)值邊和：mincost=%d\n",mincost);printf("\n最小樹的邊數(shù)：%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("請輸入結(jié)點個數(shù)：”)；scanf("%d",&length);for(i=0；i<length；i++){set[i].num=i；set[i].tag=-1；}printf("請輸入邊的權(quán)值，若不相鄰則輸入-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);/*提出權(quán)值大于0的邊數(shù)*/InsertSort(