最小生成樹實驗報告

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