最小生成樹實驗報告

數(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)采用多種。求解算法多種?；竟δ茉趎個城市之間建設(shè)網(wǎng)絡(luò)，只需要架設(shè)n-1條線路，建立最小生成樹即可實現(xiàn)最經(jīng)濟的架設(shè)方法。程序可利用克魯斯卡爾算法或prim算法生成最小生成樹。輸入輸出以文本形式輸出最小生成樹，同時輸出它們的權(quán)值。通過人機對話方式即用戶通過自行選擇命令來輸入數(shù)據(jù)和生成相應(yīng)的數(shù)據(jù)結(jié)果。二、概要設(shè)計設(shè)計思路：因為是最小生成樹問題，所以采用了課本上介紹過的克魯斯卡爾算法和prim算法兩種方法來生成最小生成樹。根據(jù)要求，需采用多種存儲結(jié)構(gòu)，所以我選擇采用了鄰接表和鄰接矩陣兩種存儲結(jié)構(gòu)。數(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,wWV且P(v,w)，＜v,w＞表示從v到w的弧，謂詞P(v,w)定義了?。紇,w＞的意義或信息}基本操作：CreateGraph(&G,V,VR)初始條件：V是圖的頂點集，VR是圖中弧的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖GoDestroyGraph(&G)初始條件：圖G存在。操作結(jié)果：銷毀圖G。LocateVex(G,u)初始條件：圖G存在，u和G中頂點有相同特征。操作結(jié)果：若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的第一個鄰接頂點。若頂點在G中沒有鄰接頂點,則返回“空”。NextAdjVex(G,v,w)初始條件：圖G存在，v是G中某個頂點，w是v的鄰接頂點。操作結(jié)果：返回v的(相對于w的)下一^鄰接頂點。若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中增添?。紇,w＞，若G是無向的，則還增添對稱弧＜v,w＞。DeleteArc(&G,v,w)初始條件：圖G存在，v和w是G中兩個頂點。操作結(jié)果：在G中刪除弧＜v,w＞，若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)：鄰接矩陣：#defineINFINITY INT_MAX據(jù)類型的定義＜1＞圖類型#defineM20#defineMAX20#definenull0#defineMAX_VERTEX_NUM20要模塊的算法描述＜1＞主函數(shù)intmain(void) owcost=0;egin；把j賦給edges[k].end；把i,j之間的權(quán)值賦給edges[k].weight；K++；}/*對結(jié)構(gòu)體edge進行初始化*/}}對圖G邊的權(quán)值進行排序sort(edges,G)；當循環(huán)變量i小于當前弧度數(shù)時{將0賦給parent[i],初始化數(shù)組；}當循環(huán)變量i小于當前弧度數(shù)時(此時第i條弧為最小的){找第i條弧的起點和終點；并分別賦給你n,m；當n,m不相等時{把m賦給parent[n]；輸出此時第i條弧的起點、終點、權(quán)值；}}}流程圖：四、調(diào)試分析本次課程設(shè)計基本達到了設(shè)計需求。但是還有很多不足。比如不能隨意切換兩種算法，也不能由用戶選擇使用鄰接矩陣還是鄰接表，以后更加深入的學(xué)習(xí)計算機知識或許可以在這兩個方面進行改進。五、測試結(jié)果prim算法正確結(jié)果: 請:先聲相也的益單<1-2> :嚼|遶艦魅叢詠馨;辺是否含其它信息唱％否心咗格區(qū)分〉32G搞點2條邊的頂點1頂點2収值似空格作為間隔”LSI量環(huán)木析生成樹的各糸邊為:<12>(235請按任意鍵繼緣…prim算法錯誤結(jié)果: 待逢擇相辿的棗曰“-站 =1嚼|齊衣待愕魯逼貞殊辿聲;邊是否含其它信息'是乩否?"空格區(qū)分八"1 八、'請輸入上條邊的頂點1頂點2權(quán)值磧空格作為間隔〉:113丄1.5克魯斯卡爾算法正確結(jié)果:溥心算kruskal溥心算kruskal.請選擇相應(yīng)的菜單<1-2>|請輸入邊數(shù)和頂點數(shù)汐3請輸入有邊的2個頂點丄2請輸入1與2之間的權(quán)值汐請輸入有邊的2個頂點13請也入1與3N間的權(quán)值油011100100權(quán)排序之后的為:?1,2?2最小生成初為：?1,2?2?1,3?4請按任意鍵繼續(xù)-克魯斯卡爾算法錯誤結(jié)果:prim算prim算「用2■用kFLiukal 請選擇相應(yīng)的菜單請輸入邊數(shù)和頂點數(shù)：21請輸入有邊的2個頂點丄1請輸入1與1之間的權(quán)值:4請輸入有邊的2個頂點t1霖給最歲的權(quán)氐技排序之后的為:?-858993460,-858993460?-858993460最小生成蔽1%：六、體會與自我評價“數(shù)據(jù)結(jié)構(gòu)”是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，它不僅是計算機學(xué)科的核心課程，而且已成為其他理工專業(yè)的熱門選修課。本學(xué)期通過學(xué)習(xí)這門課程,我學(xué)會了分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以及算法的事件分析和空間分析。這些幫助我在設(shè)計程序的過程中，更好為數(shù)據(jù)選擇適當?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算法的代碼，所以克魯斯卡爾算法還需要自己使用百度進行查找。在查找到算法之后，要將其變?yōu)槌绦蛟创a，將它們的功能實現(xiàn)出來。這就需要用到計算機高級語言編程了。我們所學(xué)的是C語言版的數(shù)據(jù)結(jié)構(gòu)，c語言的課程是