數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--最小生成樹(shù)

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：22 大?。?91.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--最小生成樹(shù)_第1頁(yè)

已閱讀1頁(yè)，還剩21頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說(shuō)明：本文檔由用戶(hù)提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告　　院系：計(jì)算機(jī)學(xué)院　　班級(jí)：軟件121班　　姓名： 　　學(xué)號(hào)： </p

2、>　　題目：最小生成樹(shù)　　指導(dǎo)老師： 　　一、引言3　　二、設(shè)計(jì)題目3

3、　　1.問(wèn)題描述3　　2.系統(tǒng)要求3　　3.測(cè)試數(shù)據(jù)4　　4.實(shí)現(xiàn)提示4　　5.參考文獻(xiàn)4

4、　　6.運(yùn)行環(huán)境5　　三、需求分析5　　1.如何選擇存儲(chǔ)結(jié)構(gòu)去建立一個(gè)帶權(quán)網(wǎng)絡(luò)。5　　2.如何在所選存儲(chǔ)結(jié)構(gòu)下輸出這個(gè)帶權(quán)網(wǎng)絡(luò)。5　　3.如何實(shí)現(xiàn)

5、PRIM算法和Kruskal算法的功能。5　　4.如何從每個(gè)頂點(diǎn)開(kāi)始找到所有的最小生成樹(shù)的頂點(diǎn)。6　　5.如何輸出最小生成樹(shù)的邊及其權(quán)值。6　　四、概要設(shè)計(jì)6　　2.圖的存儲(chǔ)結(jié)構(gòu)7&

6、lt;b>　　3.流程圖7　　五、詳細(xì)設(shè)計(jì)8　　1.主函數(shù)模塊8　　2.對(duì)路徑權(quán)值進(jìn)行排序9　　六、調(diào)試與分析13&l

7、t;b>　　七、測(cè)試結(jié)果16　　八、設(shè)計(jì)心得體會(huì)16　　附錄（源代碼）17　　摘要　　最小生成樹(shù)是數(shù)據(jù)結(jié)構(gòu)中圖的一種重要應(yīng)用，在圖中對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹(shù)，最小生成樹(shù)就是在所有生成

8、樹(shù)中總的代價(jià)最小的生成樹(shù)。本課程設(shè)計(jì)是以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu),分別采用Prim和Kruskal算法求最小生成樹(shù)。Kruskal算法和Prim算法是求最小生成樹(shù)的常用算法它們分別適用于稠密圖和稀疏圖。最小生成樹(shù)的應(yīng)用非常的廣，如礦井通風(fēng)設(shè)計(jì)和改造最優(yōu)化方面以及如何搭建最短的網(wǎng)絡(luò)線纜, 構(gòu)建造價(jià)最低的通訊網(wǎng)絡(luò) 。　　一、引言</p&

9、gt;　　本課程設(shè)計(jì)我們要解決的問(wèn)題是圖最小生成樹(shù)問(wèn)題。要用到圖的先相關(guān)數(shù)據(jù)結(jié)構(gòu)和求最小生成樹(shù)的兩種數(shù)據(jù)結(jié)構(gòu)算法普里姆算法和克魯斯卡爾算法，以及儲(chǔ)存圖的邊和點(diǎn)的鄰接矩陣。 　　本課程設(shè)計(jì)要解決的問(wèn)題構(gòu)造連通網(wǎng)的最小生成樹(shù) ,我們首先要做的是創(chuàng)建一個(gè)鄰接矩陣，用以來(lái)存儲(chǔ)圖，然后我們要想好怎樣利用普里姆算法和克魯斯卡爾算法來(lái)構(gòu)造最小生成樹(shù)。把這兩種算法寫(xiě)入主

10、函數(shù)，調(diào)試好程序。最后寫(xiě)好報(bào)告。　　二、設(shè)計(jì)題目　　1.問(wèn)題描述　　若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要假設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹(shù)問(wèn)題。<

11、;b>　　2.系統(tǒng)要求　　利用克魯斯卡爾算法求網(wǎng)的最小生成樹(shù)。　　利用普里姆算法求網(wǎng)的最小生成樹(shù)。　　要求輸出各條邊及它們的權(quán)值。　　3.測(cè)試數(shù)據(jù)

12、　4.實(shí)現(xiàn)提示　　通信線路一旦建成，必然是雙向的。因此，構(gòu)造最小生成樹(shù)的網(wǎng)一定是無(wú)向圖。設(shè)圖的頂點(diǎn)數(shù)不超過(guò)30個(gè)，并為簡(jiǎn)單起見(jiàn)，網(wǎng)中邊的權(quán)值設(shè)成小于100的整數(shù)，100則表示沒(méi)有路徑。　　5.參考文獻(xiàn)　　[1] 嚴(yán)蔚敏. 數(shù)

13、據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M]. 北京：清華大學(xué)出版社,1997. 　　[2] 譚浩強(qiáng). C程序設(shè)計(jì)（第三版）[M]. 北京：清華大學(xué)出版社，2005.1.　　[3] 二霍紅衛(wèi)算法設(shè)計(jì)與分析〔」西安西安電子科技大學(xué)出版社，2005.113-127.

14、;　　[4] 陳杰.計(jì)算機(jī)專(zhuān)業(yè)課程設(shè)計(jì)中的需求分析[J].集美大學(xué)學(xué)報(bào)，2009，10(2)：89—92. 　　[5] 高一凡. 數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析[M ]. 西安:西安電子科技大學(xué)出版社, 2002 　　6

15、.運(yùn)行環(huán)境　　VC++6.0　　三、需求分析 　　1.如何選擇存儲(chǔ)結(jié)構(gòu)去建立一個(gè)帶權(quán)網(wǎng)絡(luò)。 　　此問(wèn)題的關(guān)鍵在于如何實(shí)現(xiàn)PRIM算法和Kruskal算法，實(shí)

16、現(xiàn)的過(guò)程中如何得到構(gòu)成最小生成樹(shù)的所有頂點(diǎn)，此外輸出也是一個(gè)關(guān)鍵問(wèn)題所在，在此過(guò)程中經(jīng)過(guò)了多次調(diào)試。　　2.如何在所選存儲(chǔ)結(jié)構(gòu)下輸出這個(gè)帶權(quán)網(wǎng)絡(luò)。　　將圖中的所有頂點(diǎn)存儲(chǔ)到一個(gè)一維數(shù)組中，通過(guò)一個(gè)二維數(shù)組用鄰接矩陣連實(shí)現(xiàn)對(duì)各邊權(quán)值的存儲(chǔ)　　3.如何實(shí)現(xiàn)PRIM算法和Kruskal算法的功能。

17、　　首先我們對(duì)prim算法的問(wèn)題進(jìn)行大致的概要分析：　　假設(shè)N=（V，{E}）是連通網(wǎng)，TE是N上最小生成樹(shù)中邊的集合。算法從U={u0}（u0∈V），TE={}開(kāi)始，重復(fù)執(zhí)行下述操作：在所有u∈U，v∈V-U的邊（u，v）∈E中找一條代價(jià)最小的邊（u0,v0）并入集合TE，同時(shí)v0并入U(xiǎn)，直至U=V為止。此時(shí)TE中必有n-1條邊，則T=(V,{TE})為N的最小生成樹(shù)。&l

18、t;/p>　　克魯斯卡爾算法從另一種途徑求網(wǎng)的最小生成樹(shù)：　　假設(shè)連通網(wǎng)N=(V,{E})，則另最小生成樹(shù)的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T=(V,{})，圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。在E中選擇代價(jià)最小的邊若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價(jià)最小的邊。以此類(lèi)推直至T中的所有頂點(diǎn)都在同一連通分量上為止。&l

19、t;/p>　　4.如何從每個(gè)頂點(diǎn)開(kāi)始找到所有的最小生成樹(shù)的頂點(diǎn)。　　對(duì)于prim算法從圖的點(diǎn)集中任取一個(gè)頂點(diǎn)作為起始頂點(diǎn)，然后找到依附于該頂點(diǎn)的所有邊選取權(quán)值最小的，依次找下去直至圖中所有頂點(diǎn)都在一個(gè)點(diǎn)集中為止。對(duì)于克魯斯卡爾算法則通過(guò)對(duì)權(quán)值進(jìn)行排序找出權(quán)值最小的頂點(diǎn)和邊并把該邊的頂點(diǎn)并入點(diǎn)集之中。　　5.如何輸出最小生成樹(shù)的

20、邊及其權(quán)值。　　通過(guò)訪問(wèn)數(shù)組來(lái)實(shí)現(xiàn)對(duì)最小生成樹(shù)邊和權(quán)值的輸出。　　四、概要設(shè)計(jì)　　1、設(shè)定圖的抽象數(shù)據(jù)類(lèi)型: ADT Graph{ 　　數(shù)據(jù)對(duì)象V:V是具有相同特性的數(shù)據(jù)元素的集合,稱(chēng)為點(diǎn)集.

21、數(shù)據(jù)關(guān)系R: R={VR} 　　VR={(v,w)|v,w屬于V,(v,w)表示v和w之間存在的路徑} 　　基本操作P: 　　CreatGraph(&G,V,VR) 　　初始條

22、件:V是圖的頂點(diǎn)集,VR是圖中弧的集合. 操作結(jié)果:按V和VR是定義構(gòu)造圖G. 　　Sort(edge* ,MGraph *) 　　初始條件: 圖G存在，各邊權(quán)值已知；操作結(jié)果:對(duì)權(quán)值進(jìn)行排序； 　　Find(int *,

23、 int ) 　　初始條件:前者為已存在的集合，后者為集合中的元素；操作結(jié)果:查找函數(shù)，確定后者所屬子集； 　　Swapn(edge *, int, int) 　　初始條件: 圖G存在，各邊權(quán)值已知；

24、　　操作結(jié)果:交換某兩個(gè)邊的權(quán)值；　　2.圖的存儲(chǔ)結(jié)構(gòu)　　typedef struct　　{ 　　int vexnum,arcnum;

25、　　}ALGraph;　　typedef struct //邊的結(jié)構(gòu)體定義　　{ 　　int begin,end; //邊的開(kāi)始和結(jié)束頂點(diǎn)　　int cost; //權(quán)值&

26、lt;/p>　　}EDGE;　　typedef struct　　{　　int edges[max][max];//　　int n,e;</b&g

27、t;　　}MGraph;　　3.流程圖　　五、詳細(xì)設(shè)計(jì)　　在該函數(shù)中有6個(gè)模塊，分別是主函數(shù)模塊、路徑權(quán)值進(jìn)行排序、交換頂點(diǎn)及權(quán)值模塊、判斷是否回環(huán)、prim

28、算法的實(shí)現(xiàn)、Kruskal算法的實(shí)現(xiàn)。　　1.主函數(shù)模塊　　ALGraph G;　　MGraph G2;　　int v,i,j;　　char a;<

29、/p>　　do　　{　　system("cls");　　cout<<"\t***********************************\n\n";&

30、lt;/p>　　cout<<"\t 1 克魯斯卡爾 \n";　　cout<<"\t 2 普里姆 \n";　　cout<<"\t

31、3 退出 \n\n";　　cout<<"\t***********************************\n";　　cout<<"請(qǐng)輸入序號(hào)：";　　cin>>a;&l

32、t;/b>　　switch(a)　　{　　case '1': MiniSpanTree_Kruskal(G);system("pause");break;

33、　　case '2': cout<<"請(qǐng)輸入結(jié)點(diǎn)數(shù)：";　　cin>>G2.n;　　for(j=1;j<=G2.n;j++)　　{　　cout<<"

34、;請(qǐng)輸入第"<<j<<"個(gè)頂點(diǎn)所有邊的權(quán)值（100代表不連通）：";　　for(i=1;i<=G2.n;i++)　　cin>>G2.edges[j][i];　　}

35、　　cout<<"請(qǐng)輸入開(kāi)始頂點(diǎn):";　　cin>>v;　　MiniSpanTree_PRTM(G2,v);system("pause");break;　　default : break;

36、　　}　　}while(a!='3');　　return 0;　　該模塊包含菜單的設(shè)計(jì)以及通過(guò)一個(gè)switch語(yǔ)句來(lái)實(shí)現(xiàn)對(duì)prim算法和Kruskal算法的實(shí)現(xiàn)。進(jìn)入主菜單后選擇相應(yīng)的序號(hào)執(zhí)行相應(yīng)的操作，

37、每進(jìn)行一步后，按任意鍵繼續(xù)進(jìn)行下一個(gè)操作可重復(fù)執(zhí)行。　　2.對(duì)路徑權(quán)值進(jìn)行排序　　void Sort(EDGE *edges,ALGraph G)　　//對(duì)帶權(quán)路徑從小到大排序　　{<b

38、>　　int i,j;　　for(i=1;i<=G.arcnum;i++)　　for(j=i;j<=G.arcnum;j++)　　if(edges[i].cost>edges[j].cost)　　Swapn(edges,i,j)

39、;　　}　　在圖中找到權(quán)值最小的邊　　3.交換頂點(diǎn)及權(quán)值　　void Swapn(EDGE *edges,int i,int j)// 交換的兩個(gè)頂點(diǎn)及權(quán)值

40、;　　{　　int temp;　　temp=edges[i].begin;　　edges[i].begin=edges[j].begin;　　edges[j].begin=temp;</p&

41、gt;　　temp=edges[i].end;　　edges[i].end=edges[j].end;　　edges[j].end=temp;　　temp=edges[i].cost;　　edges[i].cost=edges[j].cost;<

42、;/p>　　edges[j].cost=temp;　　}　　該模塊主要用于Kruskal算法，找到圖中權(quán)值最小的一條邊，然后交換它們的頂點(diǎn)和權(quán)值。　　4.判斷是否回環(huán)

43、　int Find(int *parents,int f)　　//判斷是否形成環(huán)　　{　　while((parents[f])>0&&(f!=parents[f]))　　f=

44、parents[f];　　return f;　　}　　在Kruskal算法中初始parents[]為0來(lái)設(shè)置訪問(wèn)未訪問(wèn)標(biāo)志，以此來(lái)判斷圖是否成環(huán)。　　5.prim算法的實(shí)現(xiàn)

45、　　void MiniSpanTree_PRTM(MGraph &G,int v)　　{　　int closedge[max];　　int lowcost[max];　　int i,j,k,min;</

46、p>　　for(i=1;i<=G.n;i++)　　{　　lowcost[i]=G.edges[v][i];　　closedge[i]=v;　　}

47、;　　for(i=1;i<G.n;i++)　　{　　min=INF;　　for(j=1;j<=G.n;j++)　　if(lowcost[j]!=0&&am

48、p;lowcost[j]<min)　　{　　min=lowcost[j];　　k=j;　　}　　printf(

49、"邊(%d,%d)權(quán)為:%d\n",closedge[k],k,min);　　lowcost[k]=0;　　for(j=1;j<=G.n;j++)　　if(G.edges[k][j]!=0&&G.edges[k][j]<lowcost[j])

50、　　{　　lowcost[j]=G.edges[k][j];　　closedge[j]=k;　　}　　}<p&

51、gt;　　}　　6.Kruskal算法的實(shí)現(xiàn)　　void MiniSpanTree_Kruskal(ALGraph &G)　　//MiniSpanTree_Kruskal()函數(shù)實(shí)現(xiàn)　　{

52、　　int i,s,v1,v2,value,bnf,edf;　　int parents[MAX_VERTEX_NUM]; 　　EDGE edges[MAX_VERTEX_NUM];　　cout<<endl<<"請(qǐng)輸入頂點(diǎn)數(shù): &q

53、uot;;　　cin>>G.vexnum; //輸入頂點(diǎn)數(shù)　　cout<<"請(qǐng)輸入邊數(shù): ";　　cin>>G.arcnum; //輸入邊數(shù)　　cout<<&q

54、uot;請(qǐng)輸入(V1和V2), 例如: (V1=1,V2=3),(V1=2,V2=4)...";　　cout<<endl; //輸入arc(v1,v2)　　for(i=1;i<=G.arcnum;++i)　　{<

55、/p>　　cout<<endl<<"請(qǐng)輸入第 "<<i<<"條邊的第一個(gè)頂點(diǎn): ";　　cin>>v1; //輸入頭頂點(diǎn)　　cout<<"請(qǐng)輸入第 "<<

56、i<<"條邊的第二個(gè)頂點(diǎn): ";　　cin>>v2; //輸入尾頂點(diǎn)　　cout<<"請(qǐng)輸入第 "<<i<<"條邊的權(quán)值 : ";　　cin>>

57、;value; //輸入邊的權(quán)值　　edges[i].begin=v1;　　edges[i].end=v2;　　while(v1<1||v1>G.vexnum||v2<1||v2>G.vexnum) //如果輸入的非法，重新輸入<p&

58、gt;　　{　　cout<<"輸入不合法，請(qǐng)重新輸入！";　　cout<<endl<<"請(qǐng)輸入第 "<<i<<"條邊的第一個(gè)頂點(diǎn): ";

59、　cin>>v1;　　cout<<"請(qǐng)輸入第 "<<i<<"條邊的第二個(gè)頂點(diǎn): ";　　cin>>v2;　　cout<<"請(qǐng)輸入第 &

60、quot;<<i<<"條邊的權(quán)值 : ";　　cin>>value;　　edges[i].begin=v1;　　edges[i].end=v2;　　}

61、;　　edges[i].cost=value;　　} 　　Sort(edges,G); //調(diào)用Sort()函數(shù)　　cout<<"按照排列好的序列逐個(gè)輸出權(quán)值"<<endl;

62、　　for(i=1;i<=G.arcnum;i++)　　cout<<edges[i].cost<<"\t";　　for(i=1;i<=G.vexnum;++i)　　parents[i]=0; /

63、/初始化array parents[]　　cout<<endl<<"最小生成樹(shù)為:"<<endl;　　for(i=1,s=1;s<=G.vexnum&&i<=G.arcnum;i++)　　{

64、　　bnf=Find(parents,edges[i].begin);　　edf=Find(parents,edges[i].end);　　if(bnf!=edf)　　{　　parents[b

65、nf]=edf;　　cout<<endl<<edges[i].begin<<"-"; //輸出最小生成樹(shù)　　cout<<edges[i].end<<"的邊為：";　　cout<<edges[i].

66、cost;　　s++;　　} 　　} 　　}　　六、調(diào)試與分

67、析　　測(cè)試數(shù)據(jù)如下圖　　求該圖的最小生成樹(shù)　　1.進(jìn)入主頁(yè)面　　2.利用克魯斯卡爾算法求最小生成樹(shù)

68、;　　選擇序號(hào)1使用克魯斯卡爾算法求圖的最小生成樹(shù)。　　輸入每條邊的頂點(diǎn)和權(quán)值　　對(duì)權(quán)值進(jìn)行排序，并且輸出最小生成樹(shù)。　　3.利用prim算法求最小生成樹(shù)　　選擇序號(hào)2用prim算法求最小生成樹(shù)。　　通過(guò)一個(gè)n階的鄰接矩陣來(lái)實(shí)現(xiàn)圖

69、的輸入　　輸入起始頂點(diǎn)然后輸出最小生成樹(shù)的各邊及其每一條邊的權(quán)值。　　4.退出程序　　選擇序號(hào)3退出程序　　七、測(cè)試結(jié)果<p&g

70、t;　　克魯斯卡爾算法求得的最小生成樹(shù)為352146　　Prim算法求得的最小生成樹(shù)為125346　　八、設(shè)計(jì)心得體會(huì)　　在我的努力下，課程設(shè)計(jì)終于完成，由于我們對(duì)數(shù)據(jù)結(jié)構(gòu)和c語(yǔ)言不是很了解，有時(shí)忽略了一些關(guān)鍵的細(xì)節(jié)，使得在編寫(xiě)程序的過(guò)程中出現(xiàn)了一些問(wèn)題。對(duì)于打字有時(shí)粗心導(dǎo)致

71、出現(xiàn)一些難以發(fā)現(xiàn)的小錯(cuò)誤，在我的耐心，細(xì)致的調(diào)試下最終使得程序能夠運(yùn)行，課程設(shè)計(jì)圓滿(mǎn)完工。 　　問(wèn)題一：求出圖中的最小值 　　現(xiàn)象：求出的最小值是0 　　原因：圖中沒(méi)有連通的兩個(gè)頂點(diǎn)之間的權(quán)值賦值為0　　問(wèn)題二：求最小生成樹(shù)時(shí)，e

72、lse語(yǔ)句需再調(diào)用一個(gè)函數(shù) 　　現(xiàn)象：對(duì)某些二叉樹(shù)能求出最小生成樹(shù)，但不能普遍適應(yīng) 　　原因：對(duì)于找最小生成樹(shù)邊的各種可能沒(méi)有考慮全面，代碼才沒(méi)有廣泛的適應(yīng)性 　　問(wèn)題三：兩個(gè)頂點(diǎn)之間的邊是否是最小生成樹(shù)的邊 　　現(xiàn)象：

73、代碼的功能不能分辨出是否是最小生成樹(shù)的邊 　　原因：把簡(jiǎn)單的代碼寫(xiě)的很復(fù)雜，從而雜亂無(wú)章出現(xiàn)錯(cuò)誤。　　在課設(shè)過(guò)程中，遇到許多問(wèn)題，通過(guò)查閱資料和課本。是我對(duì)數(shù)據(jù)結(jié)構(gòu)有了更進(jìn)一步的認(rèn)識(shí)。當(dāng)然，這中間也有其他人的幫助。我的同學(xué)，以及指導(dǎo)老師都給我提出了非常寶貴的意見(jiàn)。通過(guò)與同學(xué)和老師的交流，使我找到了數(shù)據(jù)結(jié)構(gòu)這門(mén)課程的學(xué)習(xí)方法。但是，我感覺(jué)這不僅僅

74、是數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)方法，他或許就是學(xué)習(xí)軟件工程這門(mén)專(zhuān)業(yè)的方法，那就是多動(dòng)手。的確如此，對(duì)于一個(gè)算法，你知道它的算法思想和用計(jì)算機(jī)實(shí)現(xiàn)它卻是另外一回事。這門(mén)課程，不僅需要我們用心去理解每一種算法的思想，更需要我們?nèi)?dòng)手來(lái)實(shí)現(xiàn)它。　　附錄（源代碼）　　#include "iostream"</p&

75、gt;　　using namespace std;　　#define MAX_VERTEX_NUM 30 //定義最大頂點(diǎn)數(shù)　　#define MAXQSIZE 100　　#define max 20　　#define INF 10

76、;　　typedef struct　　{ 　　int vexnum,arcnum;　　}ALGraph;　　typedef struct //邊的結(jié)構(gòu)體定義

77、;　　{ 　　int begin,end; //邊的開(kāi)始和結(jié)束頂點(diǎn)　　int cost; //權(quán)值　　}EDGE;　　///////////////////////////

78、///　　typedef struct　　{　　int edges[max][max];//　　int n,e;　　}MGraph;&l

79、t;/b>　　void Swapn(EDGE *edges,int i,int j); // 交換的兩個(gè)頂點(diǎn)及權(quán)值　　void Sort(EDGE *edges,ALGraph G); //對(duì)帶權(quán)路徑從小到大排序　　int Find(int *parents,int f);

80、 //判斷是否形成環(huán)　　void MiniSpanTree_Kruskal(ALGraph &G); //MiniSpanTree_Kruskal()函數(shù)實(shí)現(xiàn)　　void Swapn(EDGE *edges,int i,int j)// 交換的兩個(gè)頂點(diǎn)及權(quán)值　　{

81、;　　int temp;　　temp=edges[i].begin;　　edges[i].begin=edges[j].begin;　　edges[j].begin=temp;　　temp=e

82、dges[i].end;　　edges[i].end=edges[j].end;　　edges[j].end=temp;　　temp=edges[i].cost;　　edges[i].cost=edges[j].cost;　　ed

83、ges[j].cost=temp;　　}　　void Sort(EDGE *edges,ALGraph G)　　//對(duì)帶權(quán)路徑從小到大排序　　{<b

84、>　　int i,j;　　for(i=1;i<=G.arcnum;i++)　　for(j=i;j<=G.arcnum;j++)　　if(edges[i].cost>edges[j].cost)　　Swapn(edges,i,j)

85、;　　}　　int Find(int *parents,int f)　　//判斷是否形成環(huán)　　{　　while((p

86、arents[f])>0&&(f!=parents[f]))　　f=parents[f];　　return f;　　}　　void MiniSpanTree_Kruskal(

87、ALGraph &G)　　//MiniSpanTree_Kruskal()函數(shù)實(shí)現(xiàn)　　{　　int i,s,v1,v2,value,bnf,edf;　　int parents[MAX_VERTEX_NUM]; <

88、/p>　　EDGE edges[MAX_VERTEX_NUM];　　cout<<endl<<"請(qǐng)輸入頂點(diǎn)數(shù): ";　　cin>>G.vexnum; //輸入頂點(diǎn)數(shù)　　cout<<"請(qǐng)輸入

89、邊數(shù): ";　　cin>>G.arcnum; //輸入邊數(shù)　　cout<<"請(qǐng)輸入(V1和V2), 例如: (V1=1,V2=3),(V1=2,V2=4)...";　　cout<<endl; //

90、輸入arc(v1,v2)　　for(i=1;i<=G.arcnum;++i)　　{　　cout<<endl<<"請(qǐng)輸入第 "<<i<<"條邊的第一個(gè)頂點(diǎn): ";

91、　　cin>>v1; //輸入頭頂點(diǎn)　　cout<<"請(qǐng)輸入第 "<<i<<"條邊的第二個(gè)頂點(diǎn): ";　　cin>>v2; //輸入尾頂點(diǎn)<p&g

92、t;　　cout<<"請(qǐng)輸入第 "<<i<<"條邊的權(quán)值 : ";　　cin>>value; //輸入邊的權(quán)值　　edges[i].begin=v1;　　edges[i].end=v2;<

93、/p>　　while(v1<1||v1>G.vexnum||v2<1||v2>G.vexnum) //如果輸入的非法，重新輸入　　{　　cout<<"輸入不合法，請(qǐng)重新輸入！";　　cou

94、t<<endl<<"請(qǐng)輸入第 "<<i<<"條邊的第一個(gè)頂點(diǎn): ";　　cin>>v1;　　cout<<"請(qǐng)輸入第 "<<i<<"條邊的第二個(gè)頂點(diǎn): &

95、quot;;　　cin>>v2;　　cout<<"請(qǐng)輸入第 "<<i<<"條邊的權(quán)值 : ";　　cin>>value;

96、edges[i].begin=v1;　　edges[i].end=v2;　　}　　edges[i].cost=value;　　} 　　Sort(edges

97、,G); //調(diào)用Sort()函數(shù)　　cout<<"按照排列好的序列逐個(gè)輸出權(quán)值"<<endl;　　for(i=1;i<=G.arcnum;i++)　　cout<<edges[i].cost<<"

98、;\t";　　for(i=1;i<=G.vexnum;++i)　　parents[i]=0; //初始化array parents[]　　cout<<endl<<"最小生成樹(shù)為:"<<endl;&

99、lt;p>　　for(i=1,s=1;s<=G.vexnum&&i<=G.arcnum;i++)　　{ 　　bnf=Find(parents,edges[i].begin);　　edf=Find(parents,edges[i].end);&

100、lt;/p>　　if(bnf!=edf)　　{　　parents[bnf]=edf;　　cout<<endl<<edges[i].begin<<"-"; //輸出最小生成樹(shù)</p&

101、gt;　　cout<<edges[i].end<<"的邊為：";　　cout<<edges[i].cost;　　s++;　　} <

102、p>　　} 　　}　　///////////////////////　　void MiniSpanTree_PRTM(MGraph &G,int v)　　{<

103、/b>　　int closedge[max];　　int lowcost[max];　　int i,j,k,min;　　for(i=1;i<=G.n;i++)　　{</p&g

104、t;　　lowcost[i]=G.edges[v][i];　　closedge[i]=v;　　}　　for(i=1;i<G.n;i++)　　{&

105、lt;p>　　min=INF;　　for(j=1;j<=G.n;j++)　　if(lowcost[j]!=0&&lowcost[j]<min)　　{　　min=l

106、owcost[j];　　k=j;　　}　　printf("邊(%d,%d)權(quán)為:%d\n",closedge[k],k,min);　　lowcost[k]=0;</p&g

107、t;　　for(j=1;j<=G.n;j++)　　if(G.edges[k][j]!=0&&G.edges[k][j]<lowcost[j])　　{　　lowcost[j]=G.edges[k][j];

108、　　closedge[j]=k;　　}　　}　　}　　int main()　　{

109、　　ALGraph G;　　MGraph G2;　　int v,i,j;　　char a;　　do<p&

110、gt;　　{　　system("cls");　　cout<<"\t***********************************\n\n";　　cout<<"\t 1 克魯

111、斯卡爾 \n";　　cout<<"\t 2 普里姆 \n";　　cout<<"\t 3 退出 \n\n";　　cou

112、t<<"\t***********************************\n";　　cout<<"請(qǐng)輸入序號(hào)：";　　cin>>a;　　switch(a)

113、;　　{　　case '1': MiniSpanTree_Kruskal(G);system("pause");break;　　case '2': cout<<"請(qǐng)輸入結(jié)點(diǎn)數(shù)：";</p

114、>　　cin>>G2.n;　　for(j=1;j<=G2.n;j++)　　{　　cout<<"請(qǐng)輸入第"<<j<<"個(gè)頂點(diǎn)所有邊的權(quán)值（100代表不連通）：&quo

115、t;;　　for(i=1;i<=G2.n;i++)　　cin>>G2.edges[j][i];　　}　　cout<<"請(qǐng)輸入開(kāi)始頂點(diǎn):";&l

116、t;b>　　cin>>v;　　MiniSpanTree_PRTM(G2,v);system("pause");break;　　default : break;　　}　　}whi

眾賞文庫(kù)> 全部分類(lèi)> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--最小生成樹(shù)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--最小生成樹(shù)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載