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

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

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

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

文檔簡介

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28、算法的實現(xiàn)、Kruskal算法的實現(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<<"請輸入序號：";　　cin>>a;&l

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

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

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

35、　　cout<<"請輸入開始頂點:";　　cin>>v;　　MiniSpanTree_PRTM(G2,v);system("pause");break;　　default : break;

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

37、每進行一步后，按任意鍵繼續(xù)進行下一個操作可重復執(zhí)行。　　2.對路徑權(quán)值進行排序　　void Sort(EDGE *edges,ALGraph G)　　//對帶權(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.交換頂點及權(quán)值　　void Swapn(EDGE *edges,int i,int j)// 交換的兩個頂點及權(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)值最小的一條邊，然后交換它們的頂點和權(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來設(shè)置訪問未訪問標志，以此來判斷圖是否成環(huán)。　　5.prim算法的實現(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算法的實現(xiàn)　　void MiniSpanTree_Kruskal(ALGraph &G)　　//MiniSpanTree_Kruskal()函數(shù)實現(xiàn)　　{

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

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

54、uot;請輸入(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<<"請輸入第 "<<i<<"條邊的第一個頂點: ";　　cin>>v1; //輸入頭頂點　　cout<<"請輸入第 "<<

56、i<<"條邊的第二個頂點: ";　　cin>>v2; //輸入尾頂點　　cout<<"請輸入第 "<<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<<"輸入不合法，請重新輸入！";　　cout<<endl<<"請輸入第 "<<i<<"條邊的第一個頂點: ";

59、　cin>>v1;　　cout<<"請輸入第 "<<i<<"條邊的第二個頂點: ";　　cin>>v2;　　cout<<"請輸入第 &

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<<"按照排列好的序列逐個輸出權(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<<"最小生成樹為:"<<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<<"-"; //輸出最小生成樹　　cout<<edges[i].end<<"的邊為：";　　cout<<edges[i].

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

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

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

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

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

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

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

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

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

75、gt;　　using namespace std;　　#define MAX_VERTEX_NUM 30 //定義最大頂點數(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; //邊的開始和結(jié)束頂點　　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); // 交換的兩個頂點及權(quán)值　　void Sort(EDGE *edges,ALGraph G); //對帶權(quán)路徑從小到大排序　　int Find(int *parents,int f);

80、 //判斷是否形成環(huán)　　void MiniSpanTree_Kruskal(ALGraph &G); //MiniSpanTree_Kruskal()函數(shù)實現(xiàn)　　void Swapn(EDGE *edges,int i,int j)// 交換的兩個頂點及權(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)　　//對帶權(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ù)實現(xiàn)　　{　　int i,s,v1,v2,value,bnf,edf;　　int parents[MAX_VERTEX_NUM]; <

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

89、邊數(shù): ";　　cin>>G.arcnum; //輸入邊數(shù)　　cout<<"請輸入(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<<"請輸入第 "<<i<<"條邊的第一個頂點: ";

91、　　cin>>v1; //輸入頭頂點　　cout<<"請輸入第 "<<i<<"條邊的第二個頂點: ";　　cin>>v2; //輸入尾頂點<p&g

92、t;　　cout<<"請輸入第 "<<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<<"輸入不合法，請重新輸入！";　　cou

94、t<<endl<<"請輸入第 "<<i<<"條邊的第一個頂點: ";　　cin>>v1;　　cout<<"請輸入第 "<<i<<"條邊的第二個頂點: &

95、quot;;　　cin>>v2;　　cout<<"請輸入第 "<<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<<"按照排列好的序列逐個輸出權(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<<"最小生成樹為:"<<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<<"-"; //輸出最小生成樹</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<<"請輸入序號：";　　cin>>a;　　switch(a)

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

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

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

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

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

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

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載