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

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

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

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

文檔簡介

1、　　目錄　　一、設計目的……………………………………………………………….-2-　　二、算法思想分析………………………………………………………-2-　　1.算法思想………………………………………………………………..-3-<

2、p>　　1）普里姆（Prim）算法思想……………………………………………………….-3-　　2）克魯斯卡爾（Kruskal）算法思想..........................................-3-　　2.系統(tǒng)采用的數(shù)據(jù)結(jié)構(gòu)和算法………………………………-3-　　三、算法的描述與實

3、現(xiàn)……………………………………………….-4-　　四、用戶手冊………………………………………………………………-7-　　五、總結(jié)…………………………………………………………………….-10-　　六、參考文獻…………………………………………………………….-10-　　七、附

4、錄（源代碼）………………………………………………...-10-　　[摘要] 選擇一顆生成樹，使之總的消費最少，也就是要構(gòu)造連通網(wǎng)的最小代價生成樹（簡稱為最小生成樹）的問題，一顆生成樹的代價就是樹上各邊的代價之和，構(gòu)造最小生成樹可以有多種算法，其中多數(shù)算法利用了MST的性質(zhì)。　　關鍵詞：最小生成樹連通圖普里姆算法克魯斯卡爾算法 MST</p&g

5、t;　　設計目的　　了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設計方法，具備初步的獨立分析和設計能力；　　初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能；　　提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；&l

6、t;p>　　訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的科學的工作方法和作風。　　算法思想分析　　該設計的要求是在n個城市之間建設網(wǎng)絡，不僅要保證連通，還要求是最經(jīng)濟的架設方法。根據(jù)克魯斯卡爾和普里姆算法的不同之處，該程序?qū)⒊鞘袀€數(shù)大于十個時應用普里姆算法求最小生成樹，而城市個數(shù)小于

7、十個時則應用克魯斯卡爾進行計算。　　算法思想　　普里姆（Prim）算法思想　　選擇從0節(jié)點開始，并選擇0節(jié)點相關聯(lián)的最小權值邊，將與這條邊相關聯(lián)的另一頂點出列；　　在出列的節(jié)點中相關聯(lián)的所有邊中選擇一條不與另一個已出列的節(jié)點相關聯(lián)的權

8、值最小的邊，并將該邊相關聯(lián)的節(jié)點出列；　　重復b)直到所有的節(jié)點出列。　　克魯斯卡爾（Kruskal）算法思想　　為了使生成樹上總的權值之和最小，應該使每一條邊上的權值盡可能的小，所以應從權值最小的邊選起，直至選出n-1條不能構(gòu)成回路的權值最小的邊位置。　　具體做法如下：

9、首先構(gòu)造一個含n個頂點的森林，然后按權值從小到大從連通圖中選擇不使森林中產(chǎn)生回路的邊加入到森林中去，直至該森林變成一棵樹為止，這棵樹便是連通圖的最小生成樹。　　由于生成樹上不允許有回路，因此并非每一條居當前最小的邊都可選。從生成樹的構(gòu)造過程可見，初始態(tài)為n個頂點分屬n棵樹，互不連通，每加入一條邊，就將兩棵樹合并為一棵樹，在同一棵樹上的兩個頂點之間自然相連通，由此判別當前權值最小邊是否可取只要判別

10、它的兩個頂點是否在同一棵樹上即可。　　系統(tǒng)采用的數(shù)據(jù)結(jié)構(gòu)和算法　　數(shù)據(jù)結(jié)構(gòu)　　Typedef int Vertextype;　　Typedef int adimatrix[MaxVertexNum][MaxVertexNum];<

11、;/p>　　Typedef int Vertextype vexlist[MaxVertexNum];　　Typedef int VexType;　　Typedef int AdjType;　　Typedef struct edgeElem edgeset[MaxVertexNum];

12、　　struct edgeElem　　{int fromvex;//頭頂點　　int endvex;//尾頂點　　int weight;//權　　};

13、　　Typedef struct　　{int n;//圖的頂點個數(shù)　　AdjType acrs[MAXVEX][MAXVEX];//邊信息　　}GraphMatrix;　　Typedef struct　　{int start_ve

14、x,stop_vex;//邊的起點和終點　　AdjType weight;//邊的權　　}Edge;　　Edge mst[5];　　算法　　Great_a

15、djmatrix();　　Great_adjmatrix2();　　Kruskal();　　out_edgeaet();　　prim();　　算法的描述與實現(xiàn)</b&g

16、t;　　Great_adjmatrix()和Great_adjmatrix2()是兩種建立圖的方法；　　克魯斯卡爾算法（Kruskal）：　　Void kruskal(GraphMatrix * pgraph,Edge mst[])　　{int i,j,min,vx,vy

17、;　　int weight,minweight;　　Edge edge;　　for(i=0;i<pgraph->n-1;i++)　　{mst[i].start_vex = 0;　　Mst[i].stop_vex = i

18、+1;　　Mst[i].weight = pgraph->arcs[0][i+1];　　}　　for(i=0;i<pgraph->n-1;i++)//共n-1條邊　　{minweight = MAX;</p&g

19、t;　　min = i;　　for(j=i;j<pgraph->n-1;j++)　　//從所有（vx,vy）（vx∈U,vy∈V-U）中選出最短的邊　　if(mst[j].weight<minweight)&l

20、t;p>　　{minweight = mst[j].weight;　　min = j;　　}　　//mst[min]是最短的邊(vx,vy)(vx∈U,vy∈V-U),將mst[min]加入最小生成樹<

21、p>　　edge = mst[min];　　mst[min] = mst[i];　　mst[i] = edge;　　vx = mst[i].stop_vex;//vx為剛加入最小生成樹的頂點的下標　　for(j=i+1;j<pgraph->n-1;j++

22、)　　{vy=mst[j].stop_vex;weight=pgraph->arcs[vx][vy];　　if(weight<mst[j].weight)　　{mst[j].weight=weight;　　mst[j].start_vex = vx;</

23、p>　　}　　}　　}　　}　　普里姆算法（Prim）：<p&

24、gt;　　void prim(adjmatrix GA,edgeset MST,int n)　　//利用prim算法從0點出發(fā)求圖的最小生成樹　?。鹖nt i,j,t,k,w,min,m;　　struct edgeElem x;　　for(i=0;i<n;i++)&

25、lt;/p>　　if(i>0) //從0點連接其余頂點　?。鸐ST[i-1].fromvex=0;　　MST[i-1].endvex=i;　　MST[i-1].weight=GA[0][i];　　}

26、　　for(k=1;k<n;k++)　　{min=MaxValue;　　m=k-1;　　for(j=k-1;j<n-1;j++)　　if(MST[j].weight<min)

27、　　{min=MST[j].weight;　　M=j;　　}//選擇從0點出發(fā)權值最小的邊　　x=MST[k-1];MST[k-1]=MST[m];MST[m]=x;//交換位置　　j=MST

28、[k-1].endvex;//定位于權值最小邊的尾頂點　　for(i=k;i<n-1;i++)//選取輕邊　　{t=MST[i].endvex;　　w=GA[j][t];　　if(w<MST[i].weight)　　{

29、MST[i].weight=w;　　MST[i].fromvex=j;　　}　　}　　}　　}&l

30、t;/b>　　out_edgeset()功能為顯示最小生成樹。　　用戶手冊　　1.運行程序，得到如下窗口：　　2.輸入頂點數(shù)，選擇算法：　　1）當輸入的頂點數(shù)小于10時，選擇Kruska

31、l算法，如下圖　　2）當輸入的頂點數(shù)大于10時，選擇Prim算法，如下圖　　五、總結(jié)　　該程序?qū)崿F(xiàn)了在n個城市之間建設網(wǎng)絡，既保證了連通性，也成為了最經(jīng)濟的架設方法。程序中應用了普里姆算法和克魯斯卡爾算法，實現(xiàn)了矩陣的輸出以及最小生成樹的輸出。不過，該程序仍有不足之處，圖的輸

32、入數(shù)據(jù)過大，易出錯，不易返回，仍需完善。　　六、參考文獻　　[1] 《數(shù)據(jù)結(jié)構(gòu)程序設計題典》李春葆編清華大學出版社　　[2] 《數(shù)據(jù)結(jié)構(gòu)（C語言版）》嚴蔚敏吳偉民編清華大學出版社　　[3] 《數(shù)據(jù)結(jié)構(gòu)課程設計》蘇仕華編機

33、械工業(yè)出版社　　七、附錄：（源代碼）　　#include<stdio.h>　　#include<stdlib.h>　　#define MaxVertexNum 12　　#define MaxEdgeN

34、um 20　　#define MaxValue 1000　　#define MAXVEX 6　　#define MAX 1e+8　　typedef int Vertextype;　　typedef int adjmatrix[Ma

35、xVertexNum][MaxVertexNum];　　typedef Vertextype vexlist[MaxVertexNum];　　typedef int VexType;　　typedef int AdjType;　　typedef struct edgeEl

36、em edgeset[MaxVertexNum]; 　　struct edgeElem　　{int fromvex;//頭頂點　　int endvex;//尾頂點　　int weight;//權　　};</

37、b>　　typedef struct {　　int n; /* 圖的頂點個數(shù) */　　/*VexType vexs[MAXVEX]; 頂點信息 */　　AdjType arcs[MAXVEX][MAX

38、VEX]; /* 邊信息 */　　} GraphMatrix;　　typedef struct{　　int start_vex, stop_vex; /* 邊的起點和終點 */　　AdjType weight; /* 邊的

39、權 */　　} Edge;Edge mst[5];　　void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e)　　{ int i,j,k,w;　　printf("輸入%d個頂點序號(0--n-1)：

40、",n);　　for(i=0;i<n;i++) //建立頂點表　　scanf("%d",&GV[i]);//讀入頂點信息　　for(i=0;i<n;i++)//建立邊表　　for(j=0;j<n;j++)//初始化邊

41、表　　if(i==j) GA[i][j]=0;　　else GA[i][j]=MaxValue;　　printf("輸入%d條無向帶權邊（序號序號權值）：\n",e);　　for(k=0;k<e;k++)//設置邊表&

42、lt;p>　　{ scanf("%d%d%d",&i,&j,&w);　　GA[i][j]=GA[j][i]=w;//對稱　　}　　}　　vo

43、id Creat_adjmatrix2(vexlist GV,adjmatrix GA,int m,int e,GraphMatrix &graph)　　{ int i,j,k,w,x,y;　　printf("輸入%d個頂點序號(0-m-1)，序號從0開始。",m);　　for(

44、i=0;i<m;i++) //建立頂點表　　{scanf("%d",&GV[i]);//讀入頂點信息　　if(GV[i]>=m) 　　{ printf("您輸入的序號有誤，請輸入0到%d-1之間的數(shù)，請重新輸入。\n",m);&l

45、t;p>　　scanf("%d",&GV[i]);}　　}　　for(i=0;i<m;i++)//建立邊表　　for(j=0;j<m;j++)//初始化邊表　　GA[i][j]=MaxVa

46、lue;　　printf("請輸入有多少條邊。\n");　　scanf("%d",&e);　　printf("輸入%d條無向帶權邊（序號序號權值）：\n",e);　　for(k=0;k<e;k+

47、+)//設置邊表　　{ scanf("%d%d%d",&i,&j,&w);　　GA[i][j]=GA[j][i]=w;//對稱　　}　　printf("您輸入的圖的存貯為下面表，

48、如果不可達則用1000表示。\n");　　graph.n =m;　　for(x=0;x<m;x++)　　{for(y=0;y<m;y++) {　　graph.arcs[x][y]=GA[x][y];　　pri

49、ntf("%-4d ",graph.arcs[x][y]);}　　printf("\n");　　}　　}　　void kruskal(GraphMatri

50、x * pgraph, Edge mst[]) {　　int i, j, min, vx, vy; 　　int weight, minweight; Edge edge;　　for (i = 0; i < pgraph->n-1; i++) {　　mst[i]

51、.start_vex = 0;　　mst[i].stop_vex = i+1;　　mst[i].weight = pgraph->arcs[0][i+1];　　}　　for (i = 0; i < pgraph->n

52、-1; i++) { /* 共n-1條邊 */　　minweight = MAX; min = i;　　for (j = i; j < pgraph->n-1; j++)/* 從所有邊(vx,vy)(vx∈U,vy∈V-U)中選出最短的邊 */　　if(mst[j].we

53、ight < minweight) {　　minweight = mst[j].weight; 　　min = j;　　}　　/* mst[min]是最短的邊(vx,vy)(vx∈U, vy

54、∈V-U)，將mst[min]加入最小生成樹 */　　edge = mst[min]; 　　mst[min] = mst[i]; 　　mst[i] = edge;　　vx = mst[i].stop_vex; /* vx為剛加入最小生成樹的頂點

55、的下標 */　　for(j = i+1; j < pgraph->n-1; j++) { /* 調(diào)整mst[i+1]到mst[n-1] */　　vy=mst[j].stop_vex; weight = pgraph->arcs[vx][vy];　　if (weight < mst[j].w

56、eight) {　　mst[j].weight = weight; 　　mst[j].start_vex = vx;　　}　　}　　}

57、　　}　　void out_edgeset(edgeset MST,int e)//顯示最小生成樹　　{ int k;　　printf("最小的消耗路線為\n");

58、　　for(k=0;k<e;k++)　　printf("(%d %d %d)\n",MST[k].fromvex,MST[k].endvex,MST[k].weight);　　}　　void prim(adjmatrix GA,ed

59、geset MST,int n)//利用prim算法從0點出發(fā)求圖的最小生成樹　　{ int i,j,t,k,w,min,m;　　struct edgeElem x;　　for(i=0;i<n;i++)　　if(i>0)//從0點連接其余頂點</p

60、>　　{ MST[i-1].fromvex=0;　　MST[i-1].endvex=i;　　MST[i-1].weight=GA[0][i];　　}　　for(k=1;k<n;k++)<

61、/p>　　{ min=MaxValue;　　m=k-1;　　for(j=k-1;j<n-1;j++)　　if(MST[j].weight<min) {min=MST[j].weight;m=j;}//選擇從0點出發(fā)權值最小

62、的邊　　x=MST[k-1];MST[k-1]=MST[m];MST[m]=x;//交換位置　　j=MST[k-1].endvex;//定位于權值最小邊的尾頂點　　for(i=k;i<n-1;i++)//選取輕邊　　{ t=MST[i].endvex;w=GA

63、[j][t];　　if(w<MST[i].weight)　　{ MST[i].weight=w;　　MST[i].fromvex=j;　　}　　}</b&g

64、t;　　}　　} 　　void main()　　{　　int n,e,i;

65、;　　int a;　　system("color 71");//改變屏幕顏色　　printf(" ┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");　　printf(" ┃㊣

66、必做題：最小生成樹㊣┃\n");　　printf(" ┃ 姓名：xxxx ┃\n");　　printf(" ┃ 學號：xxxxxxxxx

67、 ┃\n");　　printf(" ┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");　　vexlist GV;//頂點表　　adjmatrix GA;//邊表　　edgeset

68、 MST;//最小生成樹　　do{　　printf("輸入圖的頂點數(shù)n，我們將根據(jù)您輸入的數(shù)據(jù)大小選擇合適的算法。\n");　　scanf("%d",&n);　　if(n>=10)

69、//大于10用prim算法來實現(xiàn)，否則kruskal算法來實現(xiàn)　　{　　printf("用prim算法從0點出發(fā)求圖的最小生成樹為：\n");　　printf("請輸入圖的邊數(shù)。\n");　　c

70、anf("%d",&e);　　Creat_adjmatrix( GV, GA, n, e);//創(chuàng)建圖　　prim(GA,MST,n);//生成最小生成樹　　out_edgeset( MST, n-1);//輸出最小生成樹

71、}　　else{　　printf("用kcuskal算法的最小生成樹為：\n");　　GraphMatrix graph;//定義一個結(jié)構(gòu)體來表示存儲結(jié)構(gòu)　　Creat_adjmatrix2(G

72、V,GA,n,e,graph);//創(chuàng)建圖　　kruskal(&graph,mst);//生成最小生成樹　　rintf("最小的消耗路線為\n");　　for (i = 0; i < graph.n-1; i++)　　printf(&qu

73、ot;(%d %d %d)\n", mst[i].start_vex,　　mst[i].stop_vex, mst[i].weight);//輸出最小生成樹　　}　　printf("謝謝使用！\n");

74、　printf("繼續(xù)？輸入1繼續(xù)，輸入0退出。\n");//方便用戶重復使用　　scanf("%d",&a); 　　getchar();　　system("cls");//清屏語句 　　}while(a

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

溫馨提示

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

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載