實驗--Kruskal算法的設(shè)計.docx

《實驗--Kruskal算法的設(shè)計.docx》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、實驗四Kruskal算法的設(shè)計[實驗?zāi)康腯１.根據(jù)算法設(shè)計需要,掌握連通網(wǎng)的靈活表示方法;２.掌握最小生成樹的Kruskal算法;３.基本掌握貪心算法的一般設(shè)計方法;４.進一步掌握集合的表示與操作算法的應(yīng)用.[預(yù)習(xí)要求]１.認真閱讀算法設(shè)計教材和數(shù)據(jù)結(jié)構(gòu)教材內(nèi)容,熟習(xí)連通網(wǎng)的不同表示方法和最小生成樹算法;２.設(shè)計Kruskal算法實驗程序#include#defineN20intV=0;inta[100];intE;typedefstructdat{intvs;intve;intweight;}DATA;DATAdata[20];intfind(inti){if(a[i]==

2、i)returna[i];elsereturnfind(a[i]);}voidsort(){inti,j;for(i=0;idata[j+1].weight){DATAt;t=data[j];data[j]=data[j+1];data[j+1]=t;}}}intKU(){inti,x,y,j=0;;intsum=0;for(i=0;i

3、ata[i].weight;a[x]=y;j++;}if(j==E-1)break;}returnsum;}voidmain(){intsum=0;ints,e,w;inti=0;scanf("%d",&E);while(scanf("%d%d%d",&s,&e,&w)!=EOF){if(s==0&&e==0&&w==0)break;data[i].vs=s;data[i].ve=e;data[i].weight=w;i++;V++;}sort();sum=KU();printf("%d",sum);}.[實驗步驟]1.設(shè)計測試問題,修改并調(diào)試程序,輸出最小生成樹的各條邊,直至正確為止;2

4、.待各功能子程序調(diào)試完畢,去掉測試程序,將你的程序整理成功能模塊存盤備用.[實驗報告要求]1.闡述實驗?zāi)康暮蛯嶒瀮?nèi)容;2.闡述Kruskal算法的原理方法;3.提交實驗程序的功能模塊;4.提供測試數(shù)據(jù)和相應(yīng)的最小生成樹.[思考與練習(xí)]1.設(shè)計由連通網(wǎng)初始邊集數(shù)組生成最小堆的算法;2.設(shè)計輸出堆頂元素,并將剩余元素調(diào)整成最小堆的算法;3.針對連通網(wǎng)初始邊集最小堆表示,設(shè)計Kruskal算法;4.采用成本鄰接矩陣表示連通網(wǎng)時,在剩余邊中如何實現(xiàn)最小成本邊的查找?采用成本鄰接矩陣表示連通網(wǎng)時,用C語言實現(xiàn)Prim算法.