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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目:??最小生成樹(shù)問(wèn)題?? ?院(系):?? 計(jì)算機(jī)工程學(xué)院 ? 學(xué)生姓名:?? ?班級(jí)：學(xué)號(hào):?起迄日期： ?指導(dǎo)教師： ???2023—2023年度第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ù)即可實(shí)現(xiàn)最經(jīng)濟(jì)的架設(shè)方法。程序可運(yùn)用克魯斯卡爾算法或prim算法生成最小生成樹(shù)。3．輸入輸出以文本形式輸出最小生成樹(shù)，同時(shí)輸出它們的權(quán)值。通過(guò)人機(jī)對(duì)話方式即用戶通過(guò)自行選擇命令來(lái)輸入數(shù)據(jù)和生成相應(yīng)的數(shù)據(jù)結(jié)果。二、概要設(shè)計(jì)１.設(shè)計(jì)思緒：由于是最小生成樹(shù)問(wèn)題，所以采用了課本上介紹過(guò)的克魯斯卡爾算法和ｐrim算法兩種方法來(lái)生成最小生成樹(shù)。根據(jù)規(guī)定，需采用多種存儲(chǔ)結(jié)構(gòu)，所以我選擇采用了鄰接表和鄰接矩陣兩種存儲(chǔ)結(jié)構(gòu)。2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：圖狀結(jié)構(gòu):ADＴＧraph{數(shù)據(jù)對(duì)象V:V是具有相同特性的數(shù)據(jù)元素的集合,稱(chēng)為頂點(diǎn)集。數(shù)據(jù)關(guān)系Ｒ:R=｛VR}VR＝{<v，w＞|ｖ，w∈V且P(v,ｗ),＜ｖ,w＞表達(dá)從ｖ到w的弧,謂詞Ｐ(v,ｗ)定義了弧<v,w>的意義或信息}基本操作:ＣreateGrapｈ(＆G,V,ＶＲ)初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖G。DeｓｔroyGraph(&Ｇ)初始條件:圖G存在。操作結(jié)果：銷(xiāo)毀圖Ｇ。LoｃaｔeVｅx(G,u)初始條件:圖G存在，u和G中頂點(diǎn)有相同特性。操作結(jié)果：若G中存在頂點(diǎn)ｕ，則返回該頂點(diǎn)在圖中位置；否則返回其它信息。ＧｅｔＶｅx（G,v)初始條件:圖Ｇ存在,v是G中某個(gè)頂點(diǎn)。操作結(jié)果:返回v的值。PuｔVeｘ(&G,v,vaｌue）初始條件：圖G存在,v是G中某個(gè)頂點(diǎn)。操作結(jié)果:對(duì)v賦值vaｌｕｅ。FｉｒstAdｊVeｘ(G,v)初始條件:圖G存在，ｖ是G中某個(gè)頂點(diǎn)。操作結(jié)果：返回ｖ的第一個(gè)鄰接頂點(diǎn)。若頂點(diǎn)在G中沒(méi)有鄰接頂點(diǎn),則返回“空”。NexｔAdjVｅx(G,v,w）初始條件:圖Ｇ存在,v是G中某個(gè)頂點(diǎn),w是v的鄰接頂點(diǎn)。操作結(jié)果：返回v的（相對(duì)于w的）下一個(gè)鄰接頂點(diǎn)。若w是v的最后一個(gè)鄰接點(diǎn),則返回“空”。IｎserｔＶex(&Ｇ,v)初始條件:圖G存在，v和圖中頂點(diǎn)有相同特性。操作結(jié)果:在圖G中增添新頂點(diǎn)v。ＤeleteＶｅx（＆G,v)初始條件：圖G存在,v是Ｇ中某個(gè)頂點(diǎn)。操作結(jié)果:刪除G中頂點(diǎn)v及其相關(guān)的弧。IｎｓertAｒc（&G，ｖ，ｗ)初始條件:圖G存在,ｖ和w是Ｇ中兩個(gè)頂點(diǎn)。操作結(jié)果：在G中增添?。紇,w>,若G是無(wú)向的,則還增添對(duì)稱(chēng)弧<ｖ,w>。DｅleteArc(&G,ｖ，w)初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。操作結(jié)果：在Ｇ中刪除弧<v，w>，若G是無(wú)向的，則還刪除對(duì)稱(chēng)弧<v,w>。DFSＴraversｅ(G,Ｖiｓit（））初始條件:圖Ｇ存在，Ｖiｓit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果:對(duì)圖進(jìn)行深度優(yōu)先遍歷。在遍歷過(guò)程中對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Ｖiｓｉt一次且僅一次。一旦visiｔ（)失敗,則操作失敗。BFSTraｖerｓｅ(G，Visｉt（）)初始條件:圖Ｇ存在，Visit是頂點(diǎn)的應(yīng)用函數(shù)。操作結(jié)果：對(duì)圖進(jìn)行廣度優(yōu)先遍歷。在遍歷過(guò)程中對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visｉｔ一次且僅一次。一旦ｖisit（)失敗，則操作失敗。}ADTGrａｐh存儲(chǔ)結(jié)構(gòu):鄰接矩陣：#defｉｎｅIＮＦIＮITYINT_MAX／/最大值無(wú)窮＃defｉnｅMAX_VEＲTEX_NUM20//最大頂點(diǎn)個(gè)數(shù)typeｄefenｕm{UDN}ＧｒapｈKiｎｄ;typeｄefstruｃｔArcCell{?VＲTｙpeadｊ;//ＶRType是頂點(diǎn)關(guān)系類(lèi)型?//對(duì)帶權(quán)圖為權(quán)值類(lèi)型 ＩnfoTyep*info；//該弧相關(guān)信息的指針}ArcCell,ＡdｊMatｒix［MAＸ＿ＶＥRTEX_NＵＭ］[MAX_VＥＲＴEX＿NＵM];tyｐｅｄefstrｕct{ VerteｘTｙpevｅxs[MAX_VERＴEX_NUM］;／/頂點(diǎn)向量 ＡｄｊMatrixarｃs;／/鄰接矩陣 ｉｎtvｅｘnｕm,ａrcｎum；//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)?GraphＫｉnｄｋind;}MＧraph;具體設(shè)計(jì)1.數(shù)據(jù)類(lèi)型的定義<1>圖類(lèi)型#deｆiｎeＭ２0＃ｄefineMAＸ20#defineｎulｌ0#dｅfｉnｅMAX_VERTEX_NUM20//最大頂點(diǎn)個(gè)數(shù)#defiｎeＭAＸ_NAME3//頂點(diǎn)字符串的最大長(zhǎng)度+１＃dｅｆｉneMAＸ＿INFO20/／相關(guān)信息字符串的最大長(zhǎng)度+1#deｆiｎｅINFINITYINT_MＡX//用整型最大值代替∞ｔyｐedefinｔVRＴｙｐe;tyｐedefcｈarInfoＴyｐe;typｅｄefｃharVertｅxTｙpe[MAＸ＿ＮＡMＥ]；／/鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)ｔｙpedeｆstruｃt{VRTypeadｊ；//頂點(diǎn)關(guān)系類(lèi)型。對(duì)無(wú)權(quán)圖,用1（是)或0(否)表達(dá)相鄰否；//對(duì)帶權(quán)圖，則為權(quán)值類(lèi)型IｎfoTｙｐｅ*ｉnｆo;//該弧相關(guān)信息的指針(可無(wú))}ArcCeｌl,ａdjMatｒix[MAＸ_VEＲTEX_NUＭ]［ＭAX_VＥＲTEX_NUM]；//圖的數(shù)據(jù)結(jié)構(gòu)tyｐedeｆsｔruct{VertｅxTｙｐevexs[MＡＸ＿VＥRＴEX_NUM]；//頂點(diǎn)向量aｄjMaｔrixａrcｓ;//鄰接矩陣ｉntｖexnｕｍ,／/圖的當(dāng)前頂點(diǎn)數(shù)arcnｕm;//圖的當(dāng)前弧數(shù)}mGraｐh;／/記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊的輔助數(shù)組定義tｙｐｅｄefstrｕct{VertexTypeadｊvｅx;VＲＴypelowｃost；}miｎsiｄe［ＭAX＿VEＲTEX_NＵM］；2.重要模塊的算法描述<1＞主函數(shù)intmaｉｎ(ｖoid）／/主函數(shù){inｔi; ｓcａnf（"%d",&i)；? switch(i）／＊選擇菜單*/?{ case１:{用prim算法求最小生成樹(shù)???}brｅak； case2：{用kruskal算法求最小生成樹(shù)}break;?dｅｆaulｔ:pｒiｎtf("\ｔ\ｔ輸入錯(cuò)誤!請(qǐng)重新輸入?。躰＂）； ｝}<２>使用pｒiｍ算法生成最小生成樹(shù)｛定義圖的數(shù)據(jù)結(jié)構(gòu);圖的構(gòu)建;{/＊prim算法求最小生成樹(shù)*／對(duì)Ｉ，j,ｋ定義;記錄從頂點(diǎn)集Ｕ到V－U的代價(jià)最小的邊的輔助數(shù)組定義；把頂點(diǎn)信息的賦給k；輔助數(shù)組初始化;令最小代價(jià)初始化為0,ｃlosedｇｅ［k].loｗcost=0;//初始,Ｕ＝{u};滿足當(dāng)循環(huán)變量i小于圖的當(dāng)前節(jié)點(diǎn)數(shù)時(shí)循環(huán)；{按照選取最小代價(jià)法則（即求clｏsedge.ｌowcoｓt的最小正值）選取當(dāng)前節(jié)點(diǎn)的下一結(jié)點(diǎn)(第ｋ頂點(diǎn)）;輸出生成樹(shù)的邊；將第k頂點(diǎn)并入Ｕ集合;滿足循環(huán)變量j小于圖的當(dāng)前點(diǎn)數(shù)時(shí)循環(huán)；｛新頂點(diǎn)并入U(xiǎn)集后重新選擇最小邊;}}}}<３>使用克魯斯卡爾算法生成最小生成樹(shù){圖的構(gòu)建并初始化{定義圖的數(shù)據(jù)結(jié)構(gòu)；申請(qǐng)節(jié)點(diǎn)空間(假如失敗則返回信息)；創(chuàng)建圖；/*kruskal算法求最小生成樹(shù)*/｛對(duì)i,j，n,ｍ,parｅnt［M]，edgeｅdgｅｓ[Ｍ]定義或初始化;滿足當(dāng)循環(huán)變量i小于圖的當(dāng)前節(jié)點(diǎn)數(shù)時(shí)循環(huán);{滿足循環(huán)變量j=ｉ+1小于圖的當(dāng)前點(diǎn)數(shù)時(shí)循環(huán)；{if（第i個(gè)頂點(diǎn)于第j個(gè)頂點(diǎn)相連)｛把ｉ賦給ｅdges[k].bｅgｉn;把j賦給eｄges［k].ｅnｄ；把ｉ,j之間的權(quán)值賦給ｅｄges[k].weiｇht;Ｋ++;｝/*對(duì)結(jié)構(gòu)體edge進(jìn)行初始化*/}}對(duì)圖Ｇ邊的權(quán)值進(jìn)行排序sorｔ(edges，G);當(dāng)循環(huán)變量i小于當(dāng)前弧度數(shù)時(shí){將0賦給parent[ｉ],初始化數(shù)組；}當(dāng)循環(huán)變量ｉ小于當(dāng)前弧度數(shù)時(shí)(此時(shí)第i條弧為最小的){找第i條弧的起點(diǎn)和終點(diǎn);并分別賦給你n，m；當(dāng)n，m不相等時(shí)｛把m賦給pａreｎt[ｎ]；輸出此時(shí)第i條弧的起點(diǎn)、終點(diǎn)、權(quán)值；}}｝流程圖:主函數(shù)主函數(shù)克魯斯卡爾算法Prim算法克魯斯卡爾算法Prim算法調(diào)試分析本次課程設(shè)計(jì)基本達(dá)成了設(shè)計(jì)需求。但是尚有很多局限性。比如不能隨意切換兩種算法，也不能由用戶選擇使用鄰接矩陣還是鄰接表，以后更加進(jìn)一步的學(xué)習(xí)計(jì)算機(jī)知識(shí)或許可以在這兩個(gè)方面進(jìn)行改善。五、測(cè)試結(jié)果prim算法對(duì)的結(jié)果：pｒim算法錯(cuò)誤結(jié)果：克魯斯卡爾算法對(duì)的結(jié)果：克魯斯卡爾算法錯(cuò)誤結(jié)果：六、體會(huì)與自我評(píng)價(jià)“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ),它不僅是計(jì)算機(jī)學(xué)科的核心課程，并且已成為其他理工專(zhuān)業(yè)的熱門(mén)選修課。本學(xué)期通過(guò)學(xué)習(xí)這門(mén)課程，我學(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é)模型是一種稱(chēng)為“圖”的數(shù)據(jù)結(jié)構(gòu)。在本課題中，每個(gè)頂點(diǎn)代表一個(gè)城市，每一條邊代表一條通信錄井,同時(shí)給每條途徑賦予權(quán)值，代表著這條途徑的建設(shè)代價(jià)。通過(guò)最小生成樹(shù)的實(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)可以建立許多不同的生成樹(shù),每一棵生成樹(shù)都可以是一個(gè)通信網(wǎng)。但是根據(jù)規(guī)定，我們需要以最少的經(jīng)費(fèi)來(lái)完畢整個(gè)通信網(wǎng)的建設(shè),于是便有了最小生成樹(shù)問(wèn)題