實(shí)驗(yàn)5最小生成樹算法的設(shè)計(jì)與實(shí)現(xiàn)參考模板

1、實(shí)驗(yàn)5最小生成樹算法的設(shè)計(jì)與實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康?、根據(jù)算法設(shè)計(jì)需要，掌握連通圖的靈活表示方法；2、掌握最小生成樹算法,如Prim、Kruskal算法；3、基本掌握貪心算法的一般設(shè)計(jì)方法；4、進(jìn)一步掌握集合的表示與操作算法的應(yīng)用。二、實(shí)驗(yàn)內(nèi)容1、認(rèn)真閱讀算法設(shè)計(jì)教材和數(shù)據(jù)結(jié)構(gòu)教材內(nèi)容，熟習(xí)連通圖的不同表示方法和最小生成樹算法；2、設(shè)計(jì)Kruskal算法實(shí)驗(yàn)程序。有n個(gè)城市可以用（n-1）條路將它們連通，求最小總路程的和。設(shè)計(jì)測(cè)試問題，修改并調(diào)試程序，輸出最小生成樹的各條邊，直至正確為止。三、Kruskal算法的原理方法邊權(quán)排序：4 316236445354556265661.初始化時(shí)：屆丁最小生成

2、樹的頂點(diǎn)U=不屆丁最小生成樹的頂點(diǎn)V=1,2,3,4,5,62.根據(jù)邊權(quán)排序，選出還沒有連接并且權(quán)最小的邊（131）,屆丁最小生成樹的頂點(diǎn)U=1,3，不屆丁最小生成樹的頂點(diǎn)V=2,4,5,6根據(jù)邊權(quán)排序，選出還沒有連接并且權(quán)最小的邊（462）,屆丁最小生成樹的頂點(diǎn)U=1,3,4,6（還沒有合在一起，有兩顆子樹），不屆丁最4.根據(jù)邊權(quán)排序，選出還沒有連接并且權(quán)最小的邊（364）,屆丁最小生成樹的頂點(diǎn)U=1,3,4,6（合在一起），不屆丁最小生成樹的頂點(diǎn)V=2,55.根據(jù)邊權(quán)排序，選出還沒有連接并且權(quán)最小的邊（364）,屆丁最小生成樹的頂點(diǎn)U=1,2,3,4,6,不屆丁最小生成樹的頂點(diǎn)V=56.根

3、據(jù)邊權(quán)排序，選出還沒有連接并且權(quán)最小的邊（364）,屆丁最小生成樹的頂點(diǎn)U=1,2,3,4,5,6此時(shí)，最小生成樹已完成四、實(shí)驗(yàn)程序的功能模塊功能模塊：boolcmp(Edgea,Edgeb);定義比較方法intgetfa(intx)；在并查集森林中找到x的祖先intsame(intx,inty);判斷祖先是否是同一個(gè)，即是否聯(lián)通voidmerge(intx,inty);合并子樹，即聯(lián)通兩子樹sort(e+1,e+m+1,cmp);對(duì)邊按邊權(quán)進(jìn)行升序排序詳細(xì)代碼：#include<iostream>#include<cstdio>#include<cstring&

4、gt;#include<algorithm>#defineMAXN_E100000#defineMAXN_V100000usingnamespacestd;structEdgeintfm,to,dist;邊的起始頂點(diǎn)，邊的到達(dá)頂點(diǎn)，邊權(quán)eMAXN_E;intfaMAXN_V,n,m;頂點(diǎn)數(shù)組，頂點(diǎn)總數(shù)，邊總數(shù)定義比較，只是邊權(quán)比較boolcmp(Edgea,Edgeb)returna.dist<b.dist;查找x的祖先intgetfa(intx)/getfa是在并查集森林中找到x的祖先if(fax=x)returnfax;elsereturnfax=getfa(fax);判

5、斷祖先是否是同一個(gè)，即是否聯(lián)通intsame(intx,inty)returngetfa(x)=getfa(y);合并兩棵樹voidmerge(intx,inty)intfax=getfa(x),fay=getfa(y);fafax=fay;intmain()inti;cout<<”請(qǐng)輸入頂點(diǎn)數(shù)目和邊數(shù)目："<<endl;cin>>n>>m;/n為點(diǎn)數(shù),m為邊數(shù)輸出頂點(diǎn)信息cout<<"各個(gè)頂點(diǎn)值依次為："<<endl;for(i=0;i<n;i+)fai=i;if(i!=0)II.co

6、ut<<fai<<cout<<endl;cout<<"請(qǐng)輸入邊的信息(例子：145從頂點(diǎn)1到頂點(diǎn)4的邊權(quán)為5)"<<endl;for(i=1;i<=m;i+)cin>>ei.fm>>ei.to>>ei.dist;/用邊集數(shù)組存放邊，方便排序和調(diào)用sort(e+1,e+m+1,cmp);對(duì)邊按邊權(quán)進(jìn)行升序排序intrst=n,ans=0;/rst表示目前的點(diǎn)共存在丁多少個(gè)集合中，初始情況是每個(gè)點(diǎn)都在不同的集合中for(i=1;i<=m&&rst>1

7、;i+)intx=ei.fm,y=ei.to;if(same(x,y)continue;/sameiS數(shù)是查詢兩個(gè)點(diǎn)是否在同一集合中elsemerge(x,y);/mergea§數(shù)用來將兩個(gè)點(diǎn)合并到同一集合中rst-;/每次將兩個(gè)不同集合中的點(diǎn)合并，都將使rst值減1ans+=ei.dist;/這條邊是最小生成樹中的邊，將答案加上邊權(quán)cout<<ans;return0;五、測(cè)試數(shù)據(jù)和相應(yīng)的最小生成樹Input:3 1026rT0法設(shè)計(jì)與分折疫檢5DMugkg3心N134535564556646266Putout:18生成樹為：*一+七、思考題1、微軟面試題一個(gè)大院子里住了

8、50戶人家，每家都養(yǎng)了一條狗，有一天他們接到通知說院子里有狗生病了，并要求所有主人在發(fā)現(xiàn)自己家狗生病的當(dāng)天就要把狗槍殺掉。然而所有主人和他們的狗都不能夠離開自己的房子，主人與主人之間也不能通過任何方式進(jìn)行溝通，他們能做的只是通過窗戶觀察別人家的狗是否生病從而判斷自己的狗病否。（就是說，每個(gè)主人只能看出其他49家的狗是不是生病，單獨(dú)看自己的狗是看不出來的）第一天沒有槍聲，第二天還是沒有槍聲，第三天傳出一陣槍聲，問有多少條狗被槍殺。答：3只假如只有一只病狗，那么當(dāng)該病狗主人第一天發(fā)現(xiàn)其他49家都是好狗時(shí)就會(huì)判斷出自己家狗是病狗，那么第一天就會(huì)有槍聲。假如有兩只病狗A和B,那么當(dāng)兩只狗主人對(duì)望時(shí)，看到了對(duì)方家里是病狗，那么他們也不會(huì)判斷出自己家狗狗是否生病，當(dāng)然第一天第二天第三天以及以后都不會(huì)有槍聲。假如有三只病狗A和B和C,那么其他47個(gè)主人都會(huì)看到3只病狗，而他們?nèi)覅s互相看到兩只病狗，第一天沒有槍聲是因?yàn)锳BC三家都看到了其他的病狗，沒有判斷初自己家狗是否生病，第二天沒有槍聲則驗(yàn)證了A確定BC兩家和他一樣也發(fā)現(xiàn)了兩只病狗，同理