實(shí)驗(yàn)5最小生成樹(shù)算法的設(shè)計(jì)與實(shí)現(xiàn)(報(bào)告)

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

2、4 52 5 61 2 63 5 65 6 61. 初始化時(shí)：屬于最小生成樹(shù)的頂點(diǎn)U=不屬于最小生成樹(shù)的頂點(diǎn)V=1，2，3，4，5，62. 根據(jù)邊權(quán)排序，選出還沒(méi)有連接并且權(quán)最小的邊（1 3 1），屬于最小生成樹(shù)的頂點(diǎn)U=1，3，不屬于最小生成樹(shù)的頂點(diǎn)V=2,4,5,63. 根據(jù)邊權(quán)排序，選出還沒(méi)有連接并且權(quán)最小的邊（4 6 2），屬于最小生成樹(shù)的頂點(diǎn)U=1，3，4，6（還沒(méi)有合在一起，有兩顆子樹(shù)），不屬于最小生成樹(shù)的頂點(diǎn)V=2,54. 根據(jù)邊權(quán)排序，選出還沒(méi)有連接并且權(quán)最小的邊（3 6 4），屬于最小生成樹(shù)的頂點(diǎn)U=1，3，4，6（合在一起），不屬于最小生成樹(shù)的頂點(diǎn)V=2,55. 根據(jù)邊權(quán)排

3、序，選出還沒(méi)有連接并且權(quán)最小的邊（3 6 4），屬于最小生成樹(shù)的頂點(diǎn)U=1，2，3，4，6,，不屬于最小生成樹(shù)的頂點(diǎn)V=56. 根據(jù)邊權(quán)排序，選出還沒(méi)有連接并且權(quán)最小的邊（3 6 4），屬于最小生成樹(shù)的頂點(diǎn)U=1，2，3，4，5，6此時(shí)，最小生成樹(shù)已完成4、 實(shí)驗(yàn)程序的功能模塊功能模塊：bool cmp(Edge a,Edge b)； /定義比較方法int getfa(int x)；/在并查集森林中找到x的祖先int same(int x,int y)； /判斷祖先是否是同一個(gè)，即是否聯(lián)通void merge(int x,int y); /合并子樹(shù)，即聯(lián)通兩子樹(shù)sort(e+1,e+m+1,c

4、mp); /對(duì)邊按邊權(quán)進(jìn)行升序排序詳細(xì)代碼：#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define MAXN_E 100000#define MAXN_V 100000using namespace std;struct Edge int fm,to,dist; /邊的起始頂點(diǎn)，邊的到達(dá)頂點(diǎn)，邊權(quán)eMAXN_E;int faMAXN_V,n,m; /頂點(diǎn)數(shù)組，頂點(diǎn)總數(shù)，邊總數(shù)/定義比較，只是邊權(quán)比較bool cmp(Edge a,Edge

5、b) return a.dist < b.dist;/查找x的祖先int getfa(int x)/getfa是在并查集森林中找到x的祖先 if(fax=x) return fax; else return fax = getfa(fax);/判斷祖先是否是同一個(gè)，即是否聯(lián)通int same(int x,int y) return getfa(x)=getfa(y);/合并兩棵樹(shù)void merge(int x,int y) int fax=getfa(x),fay=getfa(y); fafax=fay;int main()int i;cout<<"請(qǐng)輸入頂點(diǎn)數(shù)目

6、和邊數(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)cout<<fai<<" "cout<<endl;cout<<"請(qǐng)輸入邊的信息（例子：1 4 5 從頂點(diǎn)1到頂點(diǎn)4的邊權(quán)為5）"<<endl; for(i=1;i<=m;i+)cin>>ei.fm&

7、gt;>ei.to>>ei.dist;/用邊集數(shù)組存放邊，方便排序和調(diào)用sort(e+1,e+m+1,cmp); /對(duì)邊按邊權(quán)進(jìn)行升序排序 int rst=n,ans=0;/rst表示目前的點(diǎn)共存在于多少個(gè)集合中，初始情況是每個(gè)點(diǎn)都在不同的集合中 for(i=1;i<=m && rst>1;i+) int x=ei.fm,y=ei.to; if(same(x,y) continue;/same函數(shù)是查詢(xún)兩個(gè)點(diǎn)是否在同一集合中 else merge(x,y);/merge函數(shù)用來(lái)將兩個(gè)點(diǎn)合并到同一集合中 rst-;/每次將兩個(gè)不同集合中的點(diǎn)合并，都將

8、使rst值減1 ans+=ei.dist;/這條邊是最小生成樹(shù)中的邊，將答案加上邊權(quán) cout<<ans; return 0;5、 測(cè)試數(shù)據(jù)和相應(yīng)的最小生成樹(shù)Input:6 101 2 61 3 11 4 52 3 52 5 63 4 53 5 63 6 44 6 25 6 6Putout:18生成樹(shù)為：七、思考題1、微軟面試題一個(gè)大院子里住了50戶(hù)人家，每家都養(yǎng)了一條狗，有一天他們接到通知說(shuō)院子里有狗生病了，并要求所有主人在發(fā)現(xiàn)自己家狗生病的當(dāng)天就要把狗槍殺掉。然而所有主人和他們的狗都不能夠離開(kāi)自己的房子，主人與主人之間也不能通過(guò)任何方式進(jìn)行溝通，他們能做的只是通過(guò)窗戶(hù)觀察別人家

9、的狗是否生病從而判斷自己的狗病否。（就是說(shuō)，每個(gè)主人只能看出其他 49家的狗是不是生病，單獨(dú)看自己的狗是看不出來(lái)的）第一天沒(méi)有槍聲，第二天還是沒(méi)有槍聲，第三天傳出一陣槍聲，問(wèn)有多少條狗被槍殺。答：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互相看到兩只病狗，第一天沒(méi)有槍聲是因?yàn)锳BC三家都看到了其他的病狗，沒(méi)有判斷初自己家狗是否