克魯斯卡爾算法求無向網(wǎng)的最小生成樹數(shù)據(jù)結(jié)構(gòu)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)上機(jī)報(bào)告（1）姓名：張可心 學(xué)號班級：1403018一、題目描述用克魯斯卡爾（Kruskal）算法求無向網(wǎng)的最小生成樹，分 析你的算法的時(shí)空復(fù)雜度，必須有過程說明。輸入：輸入數(shù)據(jù)第一行為兩個(gè)正整數(shù)n和m，分別表示頂點(diǎn)數(shù)和邊 數(shù)。后面緊跟m行數(shù)據(jù)，每行數(shù)據(jù)是一條邊的信息，包括三 個(gè)數(shù)字，分別表示該邊的兩個(gè)頂點(diǎn)和邊上的權(quán)值。輸出：按順序輸出Kruskal算法求得的最小生成樹的邊集，每行一 條邊，包括三個(gè)數(shù)字，分別是該邊的兩個(gè)頂點(diǎn)和邊上的權(quán)值， 其中第一個(gè)頂點(diǎn)的編號應(yīng)小于第二個(gè)頂點(diǎn)的編號。示例輸入8 112 34 5 TOC o 1-5 h z 6 184 75 6

2、5 108 206 1547115785812示例輸出123145256578351058124615二、解題思路假定每對頂點(diǎn)表示圖的一條邊，每條邊對應(yīng)一個(gè)權(quán)值;輸入每條邊的頂點(diǎn)和權(quán)值；輸入每條邊后，計(jì)算出最小生成樹；打印最小生成樹邊的頂點(diǎn)及權(quán)值。三、源代碼#include#includetypedef struct (int a,b,value；node；int stcmp(const void *p,const void *q)(node *a=(node *)p;node *b=(node *)q;if(a-valueb-value)return 1;else if(a-value=b-

3、value)return 0;elsereturn -1;int root(int a,int *b)for(;a!=ba;a=ba);return a；bool isgroup(int a,int b,int *c)( if(root(a,c)=root(b,c)return true； return false；void add(int a,int tob,int *c)( croot(a,c)=root(tob,c)；int main ()(int n,m;scanf(%d %d”,&n,&m);node nom;for(int u=0;um;u+)scanf(%d,&(nou.a);s

4、canf(%d,&(nou.b);scanf(%d,&(nou.value);qsort(no,m,sizeof(no0),stcmp);int bcjn+1;for(int u=1;u=n;u+) bcju=u;int i=0;int cc=n;for(;im;i+)if(!isgroup(noi.a,noi,b,bcj) add(noi.a,noi.b,bcj);cc;printf(%d %d %dn,noi.a,noi.b,noi.value);if(cc=1)break;return 0;四、運(yùn)行結(jié)果C:Program Files (x86)Dev-CppConsolePauser.exeB 1112 314 5 TOC o 1-5 h z 6 184 75 65 108 206 157 117 88 1212 314 55 G5 7 85 105 8 126 15