1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計說明書最小生成樹普里姆算法的實現(xiàn)學生姓名 張通 學 號 班 級 信管1101 成 績 指導教師 曹陽 數(shù)學與計算機科學學院2013年3月15日 課程設(shè)計任務(wù)書20122013學年第二學期課程設(shè)計名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 課程設(shè)計題目： 最小生成樹普里姆算法的實現(xiàn) 完 成 期 限：自 2013年 3 月4日至 2013年 3 月 15 日共 2 周設(shè)計內(nèi)容：圖論中，對于個帶權(quán)的連通圖，其每個生成樹所有邊上的權(quán)值之和可能不同，把其所有邊上權(quán)值之和最小的生成樹稱為圖的最小生成樹。通訊線路鋪設(shè)造價最優(yōu)問題就是最小生成樹的實際應(yīng)用。 普里姆算法的的基本思想：從連通網(wǎng)N=V,E中的某一

2、頂點U0出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(U0,v)，將其頂點加入到生成樹的頂點集合U中。以后每一步從一個頂點在U中，而另一個頂點不在U中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂點加入到集合U中。如此繼續(xù)下去，直到網(wǎng)中的所有頂點都加入到生成樹頂點集合U中為止。 本課程設(shè)計中主要完成以下內(nèi)容： 1.任意給出一個帶權(quán)值的連通網(wǎng)絡(luò)圖，能夠遍歷圖中的所有節(jié)點。 2. 根據(jù)普里姆算法思想，編程實現(xiàn)此連通圖的最小生成樹的輸出。 3.計算討論算法的時間復雜度及空間復雜度。 基本要求如下： 1.程序設(shè)計界面友好；2.設(shè)計思想闡述清晰；3.算法流程圖正確；4.軟件測試方案合理、有效。 指導教師： 教研

3、室負責人： 課程設(shè)計評閱評語： 指導教師簽名： 年 月 日 摘 要 最短路徑的問題在現(xiàn)實生活中應(yīng)用非常廣泛，如郵遞員送信、公路造價等問題。本設(shè)計以VC+作為開發(fā)平臺，C語言作為編程語言，以鄰接矩陣作為存儲結(jié)構(gòu)，編程實現(xiàn)了最短路徑算法。該程序操作簡單，具有一定的應(yīng)用性。關(guān)鍵詞：最短路徑；普里姆算法；最小生成樹；VC+目 錄1 課題描述12 算法描述22.1 算法思想22.2 普里姆算法分析43 流程圖54 源代碼15 程序測試5參考文獻91 課題描述 日常生活中，人們都希望花最少的時間或者最少的金錢將一件事情辦成，例如：一個郵遞員想走最短的路把手中的物件送到收件人手中，通信公司想花費最少的金錢把

4、通信網(wǎng)絡(luò)覆蓋在n個城市之間，這些都可歸納為求最短路徑問題。 本課題利用普里姆算法來實現(xiàn)譬如通信網(wǎng)絡(luò)中各種連接方式中的最短路徑問題，從而達到一條最優(yōu)線路，以使金錢或時間的花費最小，達到解決成本的目的。 開發(fā)工具：visual c+ 6.02 算法描述 本設(shè)計是基于最小生成樹普里姆算法的思想上，以實現(xiàn)在網(wǎng)絡(luò)中可以選擇出最短線路，從而達到省時省力的效果。2.1 算法思想普利姆算法求最小生成樹的主要思想此算法是普利姆與1957年提出的一種構(gòu)造最小生成樹的算法，主要思想是：假設(shè)N=（V，E）是連通網(wǎng)，TE是N上最小生成樹中邊的集合。算法從U=u0( u0V),TE=開始，重復執(zhí)行下述操作：在所有uU,v

5、V-U的邊（u,v）E中找一條代價最小的邊（u0,v0）并入集合TE，同時v0并入U，直至U=V為止。此時TE中必有n-1條邊，則T=（V，E）為N的最小生成樹。 最小生成樹是指在所有生成樹中，邊上權(quán)值之和最小的生成樹，另外最小生成樹也可能是多個，他們之間的權(quán)值之和相等。 V1V1V2V4 6 5 1V4V2 1V3 5V3 5 3 2V5 4V6V6V5 6 6 (a) (b)V1V1 V2V4V4 1V2 1V3 V3 1 4 2V5V6 4V6V5 (c) (d) V1V1 V4V2 1V4V2 1V3 5V3 5 2 3 2V5 4 4V6V5V6 (e) (f) 2.1普里姆算法構(gòu)造

6、最小生成樹的過程2.2 普里姆算法分析在其算法中，首先，初始化一個圖給參數(shù)g,然后定義closedge用于存放最小生成樹中的頂點，調(diào)用函數(shù)Locate()求出起點u在頂點向量表中的位置，初始化U=u，利用for循環(huán)對V-U中的頂點i,初始化，再利用for循環(huán)找n-1條邊，其中，調(diào)用函數(shù)Minium()求出輔助數(shù)組中權(quán)值最小的邊, 并將其在輔助數(shù)組中的相應(yīng)位置返回到主調(diào)函數(shù)中，最后，輸出起點、終點和權(quán)值。void MiniSpanTree_PRIM(MGraph G,Vertex u) int i,j,k; minside closedge; k=LocateVex(G,u); for(j=0;

7、jG.vexnum;+j) /輔助數(shù)組初始化 if(j!=k) strcpy(closedgej.adjvex,u); closedgej.lowcost=G.arcskj; closedgek.lowcost=0; /*將頂點vk加入生成樹中*/ printf(最小代價生成樹的各條邊為:n); for(i=1;iG.vexnum;+i) k=minimum(closedge,G); printf(%s-%s)n,closedgek.adjvex,G.vexsk); /*輸出最小邊及權(quán)值*/ closedgek.lowcost=0; for(j=0;jG.vexnum;+j) if(G.arc

8、skjclosedgej.lowcost) strcpy(closedgej.adjvex,G.vexsk); closedgej.lowcost=G.arcskj; /*修改權(quán)值域*/ 分析上述算法，假設(shè)網(wǎng)中有n個點，則第一個初始化的循環(huán)語句的頻率為n，第二個循環(huán)語句的頻率為n-1。其中兩個內(nèi)循環(huán)：其一是在closedgek.lowcost中求最小值，其頻率為n-1,其二是重新選擇具有最小代價的邊，其頻率是n。由此，普利姆算法的時間復雜度為O(n2),與網(wǎng)中邊數(shù)無關(guān)。3 流程圖通過上述分模塊的概要設(shè)計，各程序模塊之間的層次（調(diào)用）關(guān)系，流程圖如下： 結(jié)束輸入number 開始 圖3.1 主函

9、數(shù)流程圖開始主函數(shù)main()caidan()=1CreateGraph(g) 調(diào)用函數(shù) caidan()=2Display(g)調(diào)用函數(shù)caidan()=3MiniSpanTree_PRIM(g,g.vexsu-1)函數(shù)調(diào)用caidan()=4breakbreakbreak退出程序圖3.2普利姆算法流程圖開始inti,j,k；jvexnum調(diào)用minimum函數(shù)，輸出成生成樹的邊k=minimum(closedge,G-vexnum);printf(n,closedgek.adjvex,k); closedgek.lowcost=0;j!=kclosedgej.adjvex=u;closed

10、gej.lowcost=G-arcsuj; closedgej.lowcost=G-arcsuj;j+closedgeu.lowcost=0;ivexnum-Yjvexnum-G-arckjarcskj;結(jié)束i+NNNj+調(diào)用函數(shù)LocateVex(G,u)輸出最小生成樹的各條邊NNYY4 源代碼 #include #include #include #include #define MAX_NAME 20 #define MAX_VERTEX_NUM 200 /*權(quán)的上限值*/ typedef char VertexMAX_NAME;/*頂點名字串*/ typedef int AdjMatr

11、ixMAX_VERTEX_NUMMAX_VERTEX_NUM;/*鄰接距陣*/ struct MGraph/*定義圖*/ Vertex vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; ; typedef struct Vertex adjvex; /*當前點*/ int lowcost; /*代價*/ minsideMAX_VERTEX_NUM; int LocateVex(MGraph G,Vertex u)/定位 int i; for(i=0;iG.vexnum;+i)if(strcmp(u,G.vexsi)=0)return

12、i; return -1; int CreateGraph(MGraph &G) int i,j,k,w; Vertex va,vb; printf(請輸入無向網(wǎng)G的頂點數(shù)和邊數(shù)(以空格為分隔)n); scanf(%d %d,&G.vexnum,&G.arcnum); if(G.vexnum=1) printf(tt最小生成樹不存在!); return 0; printf(請輸入%d個頂點的值(%d個字符):n,G.vexnum,MAX_NAME); for(i=0;iG.vexnum;+i) /* 構(gòu)造頂點集*/ scanf(%s,G.vexsi); for(i=0;iG.vexnum;+i

13、) /*初始化鄰接矩陣*/ for(j=0;jG.vexnum;+j) G.arcsij=0x7fffffff; printf(請輸入%d條邊的頂點1 頂點2 權(quán)值(以空格作為間隔): n,G.arcnum); for(k=0;kG.arcnum;+k) scanf(%s%s%d%*c,va,vb,&w); i=LocateVex(G,va); j=LocateVex(G,vb); G.arcsij=G.arcsji=w; /*對稱*/ int minimum(minside SZ,MGraph G) int i=0,j,k,min; while(!SZi.lowcost)i+; min=SZ

14、i.lowcost; /*將最小權(quán)值記在min中*/ k=i; /*把與邊關(guān)聯(lián)的生成樹外的頂點序號記在k中*/ for(j=i+1;j0&minSZj.lowcost) min=SZj.lowcost; k=j; return k; void MiniSpanTree_PRIM(MGraph G,Vertex u) int i,j,k; minside closedge; k=LocateVex(G,u); for(j=0;jG.vexnum;+j) if(j!=k) strcpy(closedgej.adjvex,u); closedgej.lowcost=G.arcskj; closedg

15、ek.lowcost=0; /*將頂點vk加入生成樹中*/ printf(最小代價生成樹的各條邊為:n); for(i=1;iG.vexnum;+i) k=minimum(closedge,G); printf(%s-%s)n,closedgek.adjvex,G.vexsk); /*輸出最小邊及權(quán)值*/ closedgek.lowcost=0; for(j=0;jG.vexnum;+j) if(G.arcskjclosedgej.lowcost) strcpy(closedgej.adjvex,G.vexsk); closedgej.lowcost=G.arcskj; /*修改權(quán)值域*/ v

16、oid Display(MGraph G) /輸出鄰接矩陣 int i,j; for(i=0;iG.vexnum;i+) printf(tt); for(j=0;j=65535) printf(t); else printf(t%d,G.arcsij); printf(n); int caidan() int number; do printf(tt* 最小生成樹布里姆算法的實現(xiàn)*n);printf(ttt* 1.建立無向圖 *n); printf(ttt* 2.鄰接矩陣的輸出 *n); printf(ttt* 3.生成最小生成樹 *n);printf(ttt* 4.退出 *n);printf(tt*n); printf(tt請選擇（先建立無向圖）:);scanf(%d,&number);if(number4|number4|number=65535)將該處勉強修改成功。 除此之外，通過本次課程設(shè)計鞏固了課本的基本知識，熟練運用課程知識。提高我們組織數(shù)據(jù)及編寫程序的能力，使我們能夠根據(jù)問題要求和數(shù)據(jù)對象的特性，學會數(shù)據(jù)組織的方法，把現(xiàn)實世界中的問題在計算機內(nèi)部表示出來并用軟件解決問題，本次實驗大大提高了我對編程的愛好。參考文獻1譚浩強