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

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

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

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

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

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

6、ut<<fai<<cout<<endl;cout<<"請輸入邊的信息(例子：145從頂點1到頂點4的邊權為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);對邊按邊權進行升序排序intrst=n,ans=0;/rst表示目前的點共存在丁多少個集合中，初始情況是每個點都在不同的集合中for(i=1;i<=m&&rst>1

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

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