最小生成樹實(shí)驗(yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目：最小生成樹問(wèn)題院〔系〕： 計(jì)算機(jī)工程學(xué)院 學(xué)生姓名:班級(jí)：學(xué)號(hào):起迄日期:指導(dǎo)教師:2011—2012年度第2學(xué)期一、需求分析1.問(wèn)題描述：在n個(gè)城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟(jì)的架設(shè)方法。存儲(chǔ)結(jié)構(gòu)采用多種。求解算法多種。2.根本功能在n個(gè)城市之間建設(shè)網(wǎng)絡(luò)，只需要架設(shè)n-1條線路，建立最小生成樹即可實(shí)現(xiàn)最經(jīng)濟(jì)的架設(shè)方法。程序可利用克魯斯卡爾算法或prim算法生成最小生成樹。3.輸入輸出以文本形式輸出最小生成樹，同時(shí)輸出它們的權(quán)值。通過(guò)人機(jī)對(duì)話方式即用戶通過(guò)自行選擇命令來(lái)輸入數(shù)據(jù)和生成相應(yīng)的數(shù)據(jù)結(jié)果。二、概要設(shè)計(jì)1.設(shè)計(jì)思路：因?yàn)槭亲钚∩蓸鋯?wèn)題，所以采用了課本上介紹過(guò)的克魯斯卡爾算法和prim算法兩種方法來(lái)生成最小生成樹。根據(jù)要求，需采用多種存儲(chǔ)結(jié)構(gòu)，所以我選擇采用了鄰接表和鄰接矩陣兩種存儲(chǔ)結(jié)構(gòu)。2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：圖狀結(jié)構(gòu)：ADTGraph{數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R={VR}VR={<v,w>|v,w∈V且P(v,w)，<v,w>表示從v到w的弧，謂詞P(v,w)定義了弧<v,w>的意義或信息}根本操作：CreateGraph(&G,V,VR)初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖G。DestroyGraph(&G)初始條件：圖G存在。操作結(jié)果：銷毀圖G。LocateVex(G,u)初始條件：圖G存在，u和G中頂點(diǎn)有相同特征。操作結(jié)果：假設(shè)G中存在頂點(diǎn)u，那么返回該頂點(diǎn)在圖中位置；否那么返回其它信息。GetVex(G,v)初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：返回v的值。PutVex(&G,v,value)初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：對(duì)v賦值value。FirstAdjVex(G,v)初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：返回v的第一個(gè)鄰接頂點(diǎn)。假設(shè)頂點(diǎn)在G中沒(méi)有鄰接頂點(diǎn)，那么返回“空”。NextAdjVex(G,v,w)初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn)。操作結(jié)果：返回v的〔相對(duì)于w的〕下一個(gè)鄰接頂點(diǎn)。假設(shè)w是v的最后一個(gè)鄰接點(diǎn)，那么返回“空”。InsertVex(&G,v)初始條件：圖G存在，v和圖中頂點(diǎn)有相同特征。操作結(jié)果：在圖G中增添新頂點(diǎn)v。DeleteVex(&G,v)初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：刪除G中頂點(diǎn)v及其相關(guān)的弧。InsertArc(&G,v,w)初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。操作結(jié)果：在G中增添弧<v,w>，假設(shè)G是無(wú)向的，那么還增添對(duì)稱弧<v,w>。DeleteArc(&G,v,w)初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。操作結(jié)果：在G中刪除弧<v,w>，假設(shè)G是無(wú)向的，那么還刪除對(duì)稱弧<v,w>。DFSTraverse(G,Visit())初始條件：圖G存在，Visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：對(duì)圖進(jìn)行深度優(yōu)先遍歷。在遍歷過(guò)程中對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，那么操作失敗。BFSTraverse(G,Visit())初始條件：圖G存在，Visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：對(duì)圖進(jìn)行廣度優(yōu)先遍歷。在遍歷過(guò)程中對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。一旦visit()失敗，那么操作失敗。}ADTGraph存儲(chǔ)結(jié)構(gòu)：鄰接矩陣：#defineINFINITYINT_MAX//最大值無(wú)窮#defineMAX_VERTEX_NUM20//最大頂點(diǎn)個(gè)數(shù)typedefenum{UDN}GraphKind;typedefstructArcCell{ VRTypeadj;//VRType是頂點(diǎn)關(guān)系類型 //對(duì)帶權(quán)圖為權(quán)值類型 InfoTyep*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{ VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)向量 AdjMatrixarcs;//鄰接矩陣 intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) GraphKindkind;}MGraph;詳細(xì)設(shè)計(jì)1.數(shù)據(jù)類型的定義<1>圖類型#defineM20#defineMAX20#definenull0#defineMAX_VERTEX_NUM20//最大頂點(diǎn)個(gè)數(shù)#defineMAX_NAME3//頂點(diǎn)字符串的最大長(zhǎng)度+1#defineMAX_INFO20//相關(guān)信息字符串的最大長(zhǎng)度+1#defineINFINITYINT_MAX//用整型最大值代替∞typedefintVRType;typedefcharInfoType;typedefcharVertexType[MAX_NAME];//鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)typedefstruct{VRTypeadj;//頂點(diǎn)關(guān)系類型。對(duì)無(wú)權(quán)圖，用1(是)或0(否)表示相鄰否；//對(duì)帶權(quán)圖，那么為權(quán)值類型InfoType*info;//該弧相關(guān)信息的指針(可無(wú))}ArcCell,adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//圖的數(shù)據(jù)結(jié)構(gòu)typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)向量adjMatrixarcs;//鄰接矩陣intvexnum,//圖的當(dāng)前頂點(diǎn)數(shù)arcnum;//圖的當(dāng)前弧數(shù)}mGraph;//記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊的輔助數(shù)組定義typedefstruct{VertexTypeadjvex;VRTypelowcost;}minside[MAX_VERTEX_NUM];2.主要模塊的算法描述<1>主函數(shù)intmain(void)//主函數(shù){inti;scanf("%d",&i); switch(i)/*選擇菜單*/{case1:{用prim算法求最小生成樹}break;case2:{用kruskal算法求最小生成樹}break;default:printf("\t\t輸入錯(cuò)誤！請(qǐng)重新輸入！\n");}}<2>使用prim算法生成最小生成樹{定義圖的數(shù)據(jù)結(jié)構(gòu)；圖的構(gòu)建；{/*prim算法求最小生成樹*/對(duì)I,j,k定義；記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊的輔助數(shù)組定義；把頂點(diǎn)信息的賦給k；輔助數(shù)組初始化；令最小代價(jià)初始化為0，closedge[k].lowcost=0;//初始,U={u}；滿足當(dāng)循環(huán)變量i小于圖的當(dāng)前節(jié)點(diǎn)數(shù)時(shí)循環(huán)；{按照選取最小代價(jià)法那么〔即求closedge.lowcost的最小正值〕選取當(dāng)前節(jié)點(diǎn)的下一結(jié)點(diǎn)〔第k頂點(diǎn)〕；輸出生成樹的邊；將第k頂點(diǎn)并入U(xiǎn)集合；滿足循環(huán)變量j小于圖的當(dāng)前點(diǎn)數(shù)時(shí)循環(huán)；{新頂點(diǎn)并入U(xiǎn)集后重新選擇最小邊；}}}}<3>使用克魯斯卡爾算法生成最小生成樹{圖的構(gòu)建并初始化{定義圖的數(shù)據(jù)結(jié)構(gòu)；申請(qǐng)節(jié)點(diǎn)空間(如果失敗那么返回信息)；創(chuàng)立圖；/*kruskal算法求最小生成樹*/{對(duì)i,j,n,m,parent[M],edgeedges[M]定義或初始化；滿足當(dāng)循環(huán)變量i小于圖的當(dāng)前節(jié)點(diǎn)數(shù)時(shí)循環(huán)；{滿足循環(huán)變量j=i+1小于圖的當(dāng)前點(diǎn)數(shù)時(shí)循環(huán)；{if(第i個(gè)頂點(diǎn)于第j個(gè)頂點(diǎn)相連){把i賦給edges[k].begin；把j賦給edges[k].end；把i，j之間的權(quán)值賦給edges[k].weight；K++；}/*對(duì)結(jié)構(gòu)體edge進(jìn)行初始化*/}}對(duì)圖G邊的權(quán)值進(jìn)行排序sort(edges,G)；當(dāng)循環(huán)變量i小于當(dāng)前弧度數(shù)時(shí){將0賦給parent[i]，初始化數(shù)組；}當(dāng)循環(huán)變量i小于當(dāng)前弧度數(shù)時(shí)(此時(shí)第i條弧為最小的){找第i條弧的起點(diǎn)和終點(diǎn)；并分別賦給你n，m；當(dāng)n，m不相等時(shí){把m賦給parent[n]；輸出此時(shí)第i條弧的起點(diǎn)、終點(diǎn)、權(quán)值；}}}流程圖：主函數(shù)主函數(shù)克魯斯卡爾算法Prim算法克魯斯卡爾算法Prim算法調(diào)試分析本次課程設(shè)計(jì)根本到達(dá)了設(shè)計(jì)需求。但是還有很多缺乏。比方不能隨意切換兩種算法，也不能由用戶選擇使用鄰接矩陣還是鄰接表，以后更加深入的學(xué)習(xí)計(jì)算機(jī)知識(shí)或許可以在這兩個(gè)方面進(jìn)行改良。五、測(cè)試結(jié)果prim算法正確結(jié)果：prim算法錯(cuò)誤結(jié)果：克魯斯卡爾算法正確結(jié)果：克魯斯卡爾算法錯(cuò)誤結(jié)果：六、體會(huì)與自我評(píng)價(jià)“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)根底，它不僅是計(jì)算機(jī)學(xué)科的核心課程，而且已成為其他理工專業(yè)的熱門選修課。本學(xué)期通過(guò)學(xué)習(xí)這門課程，我學(xué)會(huì)了分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以及算法的事件分析和空間分析。這些幫助我在設(shè)計(jì)程序的過(guò)程中，更好為數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法。通常情況下，交通、道路問(wèn)題的數(shù)學(xué)模型是一種稱為“圖”的數(shù)據(jù)結(jié)構(gòu)。在本課題中，每個(gè)頂點(diǎn)代表一個(gè)城市，每一條邊代表一條通信錄井，同時(shí)給每條路徑賦予權(quán)值，代表著這條路徑的建設(shè)代價(jià)。通過(guò)最小生成樹的實(shí)現(xiàn)，可以實(shí)現(xiàn)以最節(jié)省經(jīng)費(fèi)的方式來(lái)建立這個(gè)通信網(wǎng)。對(duì)于n個(gè)頂點(diǎn)的聯(lián)通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以是一個(gè)通信網(wǎng)。但是根據(jù)要求，我們需要以最少的經(jīng)費(fèi)來(lái)完成整個(gè)通信網(wǎng)的建設(shè)，于是便有了最小生成樹問(wèn)題。為了完本錢次課程設(shè)計(jì)，因?yàn)檎n本上只有prim算法的代碼，所以克魯斯卡爾算法還需要自己使用百度進(jìn)行查找。在查找到算法之后