資源描述:
《克魯斯卡爾算法實(shí)驗(yàn)報(bào)告》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)原理:Kruskal算法是一種按照?qǐng)D中邊的權(quán)值遞增的順序構(gòu)造最小生成樹(shù)的方法。其基本思想是:設(shè)無(wú)向連通網(wǎng)為G=(V,E),令G的最小生成樹(shù)為T(mén),其初態(tài)為T(mén)=(V,{}),即開(kāi)始時(shí),最小生成樹(shù)T由圖G中的n個(gè)頂點(diǎn)構(gòu)成,頂點(diǎn)之間沒(méi)有一條邊,這樣T中各頂點(diǎn)各自構(gòu)成一個(gè)連通分量。然后,按照邊的權(quán)值由小到大的順序,考察G的邊集E中的各條邊。若被考察的邊的兩個(gè)頂點(diǎn)屬于T的兩個(gè)不同的連通分量,則將此邊作為最小生成樹(shù)的邊加入到T中,同時(shí)把兩個(gè)連通分量連接為一個(gè)連通分量;若被考察邊的兩個(gè)頂點(diǎn)屬于同一個(gè)連通分量,則舍去此邊,以免造成回路,
2、如此下去,當(dāng)T中的連通分量個(gè)數(shù)為1時(shí),此連通分量便為G的一棵最小生成樹(shù)。如教材153頁(yè)的圖4.21(a)所示,按照Kruskal方法構(gòu)造最小生成樹(shù)的過(guò)程如圖4.21所示。在構(gòu)造過(guò)程中,按照網(wǎng)中邊的權(quán)值由小到大的順序,不斷選取當(dāng)前未被選取的邊集中權(quán)值最小的邊。依據(jù)生成樹(shù)的概念,n個(gè)結(jié)點(diǎn)的生成樹(shù),有n-1條邊,故反復(fù)上述過(guò)程,直到選取了n-1條邊為止,就構(gòu)成了一棵最小生成樹(shù)。實(shí)驗(yàn)?zāi)康模罕緦?shí)驗(yàn)通過(guò)實(shí)現(xiàn)最小生成樹(shù)的算法,使學(xué)生理解圖的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)表示,并能理解最小生成樹(shù)Kruskal算法。通過(guò)練習(xí),加強(qiáng)對(duì)算法的理解,提高編程能力。實(shí)驗(yàn)內(nèi)容
3、:(1)假定每對(duì)頂點(diǎn)表示圖的一條邊,每條邊對(duì)應(yīng)一個(gè)權(quán)值;(2)輸入每條邊的頂點(diǎn)和權(quán)值;(3)輸入每條邊后,計(jì)算出最小生成樹(shù);(4)打印最小生成樹(shù)邊的頂點(diǎn)及權(quán)值。實(shí)驗(yàn)器材(設(shè)備、元器件):PC機(jī)一臺(tái),裝有C語(yǔ)言集成開(kāi)發(fā)環(huán)境。數(shù)據(jù)結(jié)構(gòu)與程序:#include#include#includeusingnamespacestd;第5頁(yè)#defineX105typedefstructEdge{intw;intx,y;}Edge;//儲(chǔ)存邊的struct,并儲(chǔ)存邊兩端的結(jié)點(diǎn)classG
4、raphNode{public:intdata;intfather;intchild;}GraphNode[X];//儲(chǔ)存點(diǎn)信息的并查集類(lèi)(點(diǎn)的值,父結(jié)點(diǎn),子結(jié)點(diǎn))Edgeedge[X*X];boolcomp(constEdge,constEdge);voidupdate(int);intmain(){intnode_num;intsum_weight=0;FILE*in=fopen("C:\Users\瑞奇\Desktop\編程實(shí)驗(yàn)\數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)\FileTemp\in.txt","r");cout<<"Readi
5、ngdatafromfile..."<>node_num;fscanf(in,"%d",&node_num);//cout<<"Pleaseinputthedataofeachnode:"<>GraphNode[i].data;fscanf(in,"%d",&GraphNode[i].data);GraphN
6、ode[i].father=GraphNode[i].child=i;}//初始化點(diǎn)集//cout<<"Pleaseinputtherelationbetweennodesinthisformatandendwith(000):"<>x>>y>>w&&w)while(fscanf(in,"%d%d%d",&x,&y,&w)!=EOF&&w)edge[tmp_cnt].w=
7、w,edge[tmp_cnt].x=x,edge[tmp_cnt++].y=y;fclose(in);sort(edge+1,edge+tmp_cnt,comp);//對(duì)邊權(quán)進(jìn)行排序cout<<"TheMinSpanTreecontainsfollowingedges:"<
8、;if(GraphNode[m].father!=m)//使用并查集對(duì)邊是否可用進(jìn)行判斷{m=GraphNode[m].father;GraphNode[m].father=GraphNode[edge[i].y].father;}GraphNod