最小生成樹(shù)課程設(shè)計(jì) (2)

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

2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題（含答案詳解+作文范文）_第1頁(yè)

已閱讀1頁(yè)，還剩13頁(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、　　目錄　　一、問(wèn)題描述1　　二、需求分析與設(shè)計(jì)1　　1、基本信息（包括頂點(diǎn)數(shù)、邊數(shù)、權(quán)值等）。1　　2、實(shí)現(xiàn)功能（城市之間距離、最小距離、最大值等）。1</p

2、>　　三、兩種算法比較1　?。ㄒ唬?、普里姆（Prim)算法:1　?。ǘ?克魯斯卡（Kruskal)算法:1　　四、算法的設(shè)計(jì)思想1　　求圖的最小生成樹(shù)主要有兩種方法：1　　(一）、算法

3、的相同點(diǎn)：1　　（二）、算法的不同點(diǎn)：2　　六、總結(jié)4　　七源代碼5　　最小生成樹(shù)　　一

4、、問(wèn)題描述　　為了解決在n個(gè)城市之間建設(shè)網(wǎng)絡(luò)，但需要保證連通，求最經(jīng)濟(jì)的架設(shè)方法；因此利用了最小生成樹(shù)的兩種算法Prim算法和kruskal算法，從而來(lái)解決此問(wèn)題。　　二、需求分析與設(shè)計(jì)　　可以計(jì)算出兩城市之間的距離、可以計(jì)算出城市之間最小距離。

5、 　　基本信息（包括頂點(diǎn)數(shù)、邊數(shù)、權(quán)值等）。　　實(shí)現(xiàn)功能（城市之間距離、最小距離、最大值等）。　　三、兩種算法比較　　、普里姆（Prim)算法:　　普利姆算法的時(shí)間復(fù)雜度為O（n2),與

6、網(wǎng)中的邊數(shù)無(wú)關(guān)因此適用于求邊稠密的網(wǎng)的最小生成樹(shù)。　?。ǘ?、克魯斯卡（Kruskal)算法:　　克魯斯卡算法恰恰相反，它的時(shí)間復(fù)雜度為O（eloge)(e為網(wǎng)中的邊的數(shù)目）。因此它適用稀疏的網(wǎng)的最小生成樹(shù)。　　算法的設(shè)計(jì)思想

7、求圖的最小生成樹(shù)主要有兩種方法：　　1. 普里姆算法;　　2.克魯斯卡算法。　　(一）、算法的相同點(diǎn)：　　都利用了頂點(diǎn)集Ｕ和Ｖ－Ｕ中頂點(diǎn)的最小值；都有一出發(fā)點(diǎn)；每次都是選出最小的值并入Ｕ中以作為過(guò)

8、渡頂點(diǎn)，而不再求其最??；都涉及最短問(wèn)題；它們都是從一個(gè)原始頂點(diǎn)開(kāi)始將頂點(diǎn)一個(gè)個(gè)按一定順序轉(zhuǎn)移到所求終點(diǎn)中都用到了輔助向量；都從頂點(diǎn)出發(fā)，并在過(guò)程中都依據(jù)了頂點(diǎn)；都包含其頂點(diǎn)連通分量；都是對(duì)網(wǎng)進(jìn)行操作；用找到的路徑將頂點(diǎn)連接起來(lái)都是樹(shù)。　　（二）、算法的不同點(diǎn)：　　普里姆算法從頂點(diǎn)集U中任一頂點(diǎn)出發(fā)到V—U中頂點(diǎn)，迪杰斯特拉算法從源點(diǎn)出發(fā)通過(guò)頂點(diǎn)Ｕ到找到Ｖ

9、—Ｕ中頂點(diǎn)的最小值；普里姆算法的出發(fā)點(diǎn)是算法的開(kāi)始點(diǎn)；而迪杰斯特拉算法的出發(fā)點(diǎn)是求最短路徑的源點(diǎn)；普里姆算法用lowcost數(shù)組，而迪杰斯特拉算法用Ｄ[ j ]=Min{D[ i ]|vi屬于頂點(diǎn)集Ｖ－Ｓ}普里姆算法解決最小生成樹(shù)，迪杰斯特拉算法解決最短路徑；普里姆算法是順著已找到的頂點(diǎn)找其余應(yīng)并入Ｕ中的頂點(diǎn)，而迪杰斯特拉算是順著頂點(diǎn)去找其余頂點(diǎn)到源點(diǎn)的最短路徑；普里姆算法的最短是兩個(gè)頂點(diǎn)集間的最短，而迪杰斯特拉算法的最短是某點(diǎn)通過(guò)一個(gè)

10、頂點(diǎn)集Ｕ到源點(diǎn)的最短。普里姆算法的最短是兩個(gè)頂點(diǎn)間的最短，而迪杰斯特拉算法的最短是某點(diǎn)到源點(diǎn)的最短。普法無(wú)需按最短的并入，它尋找并入U(xiǎn)的點(diǎn)的依據(jù)是在U和V-U之間的最短路徑。迪法在找到最短路徑后，還要對(duì)其余結(jié)點(diǎn)的當(dāng)前最短路徑進(jìn)行修改，而普法則不進(jìn)行修改。普法是從頂點(diǎn)集的思路出發(fā)，而迪法則是按路徑長(zhǎng)度遞增思路出發(fā)。普法的出發(fā)點(diǎn)是任意的，而迪法的出發(fā)點(diǎn)是規(guī)定的。　　普法在執(zhí)行過(guò)程中不改變兩點(diǎn)間的權(quán)值

11、，而迪法在執(zhí)行過(guò)程中會(huì)求出一個(gè)或者是兩點(diǎn)的權(quán)值或者是權(quán)值之和作為最短的路徑；迪法具有方向性，而普法則可以不具有.　　系統(tǒng)測(cè)試　　/*建立圖的鄰接矩陣*/　　void CreatMatrix(adjmatrix GA){　　int i,

12、j,k,e;　　printf("圖中有%d個(gè)頂點(diǎn)\n",n);　　for(i=1;i<=n;i++){　　for(j=1;j<=n;j++){　　if(i==j){<p&g

13、t;　　GA[i][j]=0; /*對(duì)角線(xiàn)的值置為0*/　　}　　else{　　GA[i][j]=MaxNum; /*其它位置的值置初始化為一個(gè)最大整數(shù)*/

14、　　}　　}　　}　　printf("請(qǐng)輸入邊的個(gè)數(shù)：");　　scanf("%d",&arcnum);

15、　　printf("請(qǐng)輸入邊的信息，按照起點(diǎn)，終點(diǎn)，權(quán)值的形式輸入：\n");　　for(k=1;k<=arcnum;k++){　　scanf("%d,%d,%d",&i,&j,&e); /*讀入邊的信息*/　　GA[i][

16、j]=e;　　GA[j][i]=e;　　}　　}　　測(cè)試結(jié)果：　　六、總結(jié)&l

17、t;/p>　　編程要很強(qiáng)的邏輯思維，難度很大，但通過(guò)這次的自己親自動(dòng)手完成課程設(shè)計(jì)后，我懂得難度很多時(shí)候是因?yàn)槲覀冏约合胂胨请y的。如果我們一開(kāi)始就把它想象的很難，就會(huì)有心理的一種暗示，這個(gè)我是不會(huì)完成的。但是只要我們有信心，克服這種心里的障礙就一定能編寫(xiě)一個(gè)好程序。所以心態(tài)很重要。通過(guò)這次課程設(shè)計(jì)，發(fā)現(xiàn)自己對(duì)知識(shí)的掌握上還是有很多欠缺的。最主要的不足之處就是再把算法的思想用程序語(yǔ)言編寫(xiě)出來(lái)，這個(gè)對(duì)我來(lái)說(shuō)有很

18、大的難度。針對(duì)這種情況可能是我平時(shí)看程序不夠多，自己練得很不夠。還有就是對(duì)于圖的存儲(chǔ)上我不是很了解，以前總是覺(jué)得圖的存儲(chǔ)有太多的方法，對(duì)于在不同種情況下該用什么樣的方法自己不太了解，對(duì)于它們的特點(diǎn)沒(méi)有深入的了解，但通過(guò)這次自己在實(shí)際當(dāng)中的練習(xí)，對(duì)于它們有了更深層次的認(rèn)識(shí)。通過(guò)這次的課程設(shè)計(jì)要我們明白了，編程只有我們有信心，就一定能完成。　　七源代碼<

19、/p>　　#include <stdio.h>　　#include<stdlib.h> 　　#define n 7　　#define MaxNum 10000 /*定義一個(gè)最大整數(shù)*/　　/*定義鄰接矩陣類(lèi)型*/<

20、;/p>　　typedef int adjmatrix[n+1][n+1]; /*0號(hào)單元沒(méi)用*/　　typedef struct{　　int fromvex,tovex;　　int weight;　　}Edges;<

21、;/b>　　typedef Edges *EdgeNode;　　int arcnum; /*邊的個(gè)數(shù)*/　　typedef struct 　　{

22、 　　char v1; 　　char v2;

23、 　　int weight; 　　}Edge; <

24、p>　　typedef struct{ 　　Edge space[100]; 　　int Elength;

25、 　　}Headtype; 　　typedef struct <

26、/p>　　{ 　　char v; 　　int flag;

27、 　　}Dgree;　　typedef struct{ 　　Dgree biao[20];　　int Glength;

28、　　}Mark;　　/*建立圖的鄰接矩陣*/　　void CreatMatrix(adjmatrix GA){　　int i,j,k,e;　　printf("圖中有%d個(gè)頂點(diǎn)\n",n);<

29、/p>　　for(i=1;i<=n;i++){　　for(j=1;j<=n;j++){　　if(i==j){　　GA[i][j]=0; /*對(duì)角線(xiàn)的值置為0*/

30、　　}　　else{　　GA[i][j]=MaxNum; /*其它位置的值置初始化為一個(gè)最大整數(shù)*/　　}　　}

31、　　}　　printf("請(qǐng)輸入邊的個(gè)數(shù)：");　　scanf("%d",&arcnum);　　printf("請(qǐng)輸入邊的信息，按照起點(diǎn)，終點(diǎn)，權(quán)值的形式輸入：\n");</p&g

32、t;　　for(k=1;k<=arcnum;k++){　　scanf("%d,%d,%d",&i,&j,&e); /*讀入邊的信息*/　　GA[i][j]=e;　　GA[j][i]=e;<b&

33、gt;　　}　　}　　/*初始化圖的邊集數(shù)組*/　　void InitEdge(EdgeNode GE,int m){　　int i;

34、　　for(i=1;i<=m;i++){　　GE[i].weight=0;　　}　　}　　/*根據(jù)圖的鄰接矩陣生成圖的邊集數(shù)組*/　　void Ge

35、tEdgeSet(adjmatrix GA,EdgeNode GE){　　int i,j,k=1;　　for(i=1;i<=n;i++){　　for(j=i+1;j<=n;j++){　　if(GA[i][j]!=0&&GA[i][j]!=Max

36、Num){　　GE[k].fromvex=i;　　GE[k].tovex=j;　　GE[k].weight=GA[i][j];　　k++;　　}</

37、p>　　}　　}　　}　　/*按升序排列圖的邊集數(shù)組*/　　void SortEdge(EdgeNode GE,int m){&l

38、t;/p>　　int i,j,k;　　Edges temp;　　for(i=1;i<m;i++){　　k=i;　　for(j=i+1;j<=m;j++){

39、;　　if(GE[k].weight>GE[j].weight){　　k=j;　　}　　}　　if(k!=i){&

40、lt;/p>　　temp=GE[i];GE[i]=GE[k];　　GE[k]=temp;　　}　　}　　}

41、　　/*利用普里姆算法從初始點(diǎn)v出發(fā)求鄰接矩陣表示的圖的最小生成樹(shù)*/　　void Prim(adjmatrix GA,EdgeNode T){　　int i,j,k,min,u,m,w;　　Edges temp;　　/*給T賦初值，對(duì)應(yīng)為v1依次到其余

42、各頂點(diǎn)的邊*/　　k=1;　　for(i=1;i<=n;i++){　　if(i!=1){　　T[k].fromvex=1;　　T[k].tovex=

43、i;　　T[k].weight=GA[1][i];　　k++;　　}　　}　　/*進(jìn)行n-1次循環(huán)，每次求出最小生成

44、樹(shù)中的第k條邊*/　　for(k=1;k<n;k++){　　min=MaxNum;　　m=k;　　for(j=k;j<n;j++){　　if(T[j].weight<min)

45、{　　min=T[j].weight;m=j;　　}　　}　　/*把最短邊對(duì)調(diào)到k-1下標(biāo)位置*/　　temp=T[k];<

46、p>　　T[k]=T[m];　　T[m]=temp;　　/*把新加入最小生成樹(shù)T中的頂點(diǎn)序號(hào)賦給j*/　　j=T[k].tovex;　　/*修改有關(guān)邊，使T中到T外的每一個(gè)頂點(diǎn)保持一條到目前為止最短的邊*/　　for(i=k

47、+1;i<n;i++){　　u=T[i].tovex;　　w=GA[j][u];　　if(w<T[i].weight){　　T[i].weight=w;T[i].fromvex=j;　　}</b

48、>　　}　　}　　}　　/*輸出邊集數(shù)組的每條邊*/　　void OutEdge(EdgeNode GE,in

49、t e){　　int i;　　printf("按照起點(diǎn)，終點(diǎn)，權(quán)值的形式輸出的最小生成樹(shù)為：\n");　　for(i=1;i<=e;i++){　　printf("%d,%d,%d\n",G

50、E[i].fromvex,GE[i].tovex,GE[i].weight);　　}　　}　　void InitMark(Mark &M,int x){　　int j;

51、　　M.Glength=x; 　　printf("請(qǐng)依次輸入這些點(diǎn):"); 　　for(j=1;j<=x;j++)

52、 　　{ 　　scanf("%s",&M.biao[j].v);

53、 　　M.biao[j].flag=-1; 　　} 　　}

54、 　　void InitHeadType(Headtype &H,int y){　　int k; 　　H.Elength=y;

55、 　　for(k=1;k<=y;k++) 　　{ 　　p

56、rintf("請(qǐng)輸入邊的關(guān)系:"); 　　scanf("%s%s%d",&H.space[k].v1,&H.space[k].v2,&H.space[k].weight); 　　}

57、 　　} 　　void HeadAdjust(Headtype &H,int s,int m)

58、 　　{Edge rc; 　　int p; &

59、lt;p>　　rc=H.space[s]; 　　for(p=2*s;p<=m;p*=2) 　　{

60、 　　if(p<m&&(H.space[p].weight<H.space[p+1].weight)) 　　++p;

61、 　　if(rc.weight>H.space[p].weight) 　　break;

62、H.space[s]=H.space[p]; 　　s=p; 　　}

63、 　　H.space[s]=rc; 　　}

64、 　　void HeadSort(Headtype &H)

65、 　　{int q; 　　Edge rb; 　　for(q=H.Elength/2;q>0;--q)

66、 　　HeadAdjust(H,q,H.Elength); 　　for(q=H.Elength;q>1;--q) <p&

67、gt;　　{ 　　rb=H.space[1]; 　　H.space[1]=H.space[q];

68、 　　H.space[q]=rb; 　　HeadAdjust(H,1,q-1);

69、　　} 　　} 　　void main()　　{

70、　　int q;　　do　　{　　printf("*******************************************************\n");&l

71、t;p>　　printf("1. 普里姆算法最小生成樹(shù)算法! \n");　　printf("2. 克魯斯卡爾算法最小生成樹(shù)算法! \n");　　printf("\n********************

72、*********************************\n");　　printf(" 制作人：岳忠全 \n");　　printf(" 班級(jí) ：網(wǎng) 絡(luò) 工程班

73、\n");　　printf(" 時(shí) 間： 2013.12.24 \n"); 　　printf("\n**************************************************** \n");

74、;　　printf("\n**************** 請(qǐng)選擇要進(jìn)行的操:! ************** \n");　　scanf("%d",&q);　　switch(q)　　{

75、　　case 1:　　adjmatrix GA;　　Edges GE[n*(n-1)/2],T[n];　　CreatMatrix(GA);　　InitEdge(GE,arc

76、num);　　GetEdgeSet(GA,GE);　　SortEdge(GE,arcnum);　　Prim(GA,T);　　printf("\n");　　OutEdge(T,n-1);&

77、lt;p>　　break;　　case 2:　　int Gnumber,Enumber,a,b,c; 　　printf("請(qǐng)輸入點(diǎn)的個(gè)數(shù):\n&q

78、uot;); 　　scanf("%d",&Gnumber); 　　printf("請(qǐng)輸入邊數(shù):");

79、 　　scanf("%d",&Enumber); 　　Headtype H; </

80、p>　　Mark M; 　　Dgree e1,e2; 　　InitMark(M,Gnumber

81、); 　　InitHeadType(H,Enumber); 　　HeadSort(H);

82、 　　printf("輸出最小生成樹(shù);\n"); 　　for(a

83、=1;a<=Enumber;a++) 　　{ 　　for(b=1;b<=Gnumber;b++)<

84、p>　　{　　if(M.biao[b].v==H.space[a].v1) 　　{　　e1=M.biao[b]; <p&g

85、t;　　break;　　}　　} 　　for(c=1;c<=Gnumber;c++)　　{

86、 　　if(M.biao[c].v==H.space[a].v2) 　　{　　e2=M.biao[c]; </p&

87、gt;　　break;　　} 　　}

88、 　　while(e1.flag!=-1)　　{　　b=e1.flag; </p&

89、gt;　　e1=M.biao[e1.flag];　　} 　　while(e2.flag!=-1)　　{　　c=e2

90、.flag; 　　e2=M.biao[e2.flag]; 　　} 　　if(e2.v!=e1.v)

91、　　{ 　　M.biao[b].flag=c; 　　printf("(%c,%c):%d\n",H.space[a].v1,

92、H.space[a].v2,H.space[a].weight); 　　}　　} break; 　　}　　}while(q!=2);&

眾賞文庫(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ù)課程設(shè)計(jì) (2)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

最小生成樹(shù)課程設(shè)計(jì) (2)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載