最小生成樹(shù)問(wèn)題

《最小生成樹(shù)問(wèn)題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、Projectl設(shè)計(jì)報(bào)告選題名稱:最小生成樹(shù)問(wèn)題學(xué)院:計(jì)算機(jī)工程學(xué)院專業(yè):計(jì)算機(jī)科學(xué)與技術(shù)NIIT班級(jí)：計(jì)算機(jī)1147姓名：劉建成學(xué)號(hào)：1141317722指導(dǎo)教師:李笑平張亞紅殷路學(xué)年學(xué)期：2015?2016學(xué)年第1學(xué)期1課題需求描述錯(cuò)誤！未定義書簽。2總體功能與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)錯(cuò)誤！未定義書簽。2.1總體功能結(jié)構(gòu)錯(cuò)誤！未定義書簽。2.2數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)4調(diào)試與測(cè)試算法設(shè)計(jì)和程序設(shè)計(jì)錯(cuò)誤！未定義書簽。5Project設(shè)計(jì)總結(jié)錯(cuò)誤！未定義書簽。參考文獻(xiàn)1:課題需求描述1.1課題題目：最小生成樹(shù)問(wèn)題：若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要假設(shè)ml條線路即可。如何以最低的經(jīng)

2、濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹(shù)問(wèn)題。1.2需求描述：（1）利用克魯斯卡爾算法求網(wǎng)的最小生成樹(shù)。（2）實(shí)現(xiàn)教材6.5節(jié)屮定義的抽象數(shù)據(jù)類型MFSeto以此表示構(gòu)造生成樹(shù)過(guò)程中的連通分量。（3）以文木的形式輸出生成樹(shù)中各條邊以及他們的權(quán)值。（ac3）5、選做內(nèi)容：利用堆排序（參見(jiàn)教科書1043節(jié)）實(shí)現(xiàn)選擇權(quán)值最小的邊數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)程序主要利用圖的結(jié)構(gòu)生成圖，再利用克魯斯卡爾算法求出最小生成樹(shù)。3：算法設(shè)計(jì)和程序設(shè)計(jì)3.1設(shè)計(jì)原理（1）通信線路一旦建立，必然是雙向的。因此，構(gòu)造生成樹(shù)的網(wǎng)一定是無(wú)向的，設(shè)圖的頂點(diǎn)個(gè)數(shù)不超過(guò)30個(gè)，并為就簡(jiǎn)單起見(jiàn)，網(wǎng)屮邊的權(quán)值設(shè)

3、成小于100的整數(shù)，可利用c語(yǔ)言提供的隨機(jī)函數(shù)產(chǎn)生。圖的存儲(chǔ)結(jié)構(gòu)的選取應(yīng)和所做操作相適應(yīng)。（2）為了便于選擇權(quán)值最小邊，此題的存儲(chǔ)結(jié)構(gòu)不應(yīng)選擇鄰接矩陣的數(shù)組表示法，也不選取鄰接表，而是以存儲(chǔ)邊（帶權(quán)）的數(shù)組表示圖。3.2概要設(shè)計(jì)1）抽象數(shù)據(jù)類型（ADT）如下：ADTGRAPH{數(shù)據(jù)對(duì)彖V：V是具有相同特性的數(shù)據(jù)元素的集合，成為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R={VR}VR={lv,w屈于V且P（v,w）,表示從v到w的弧，謂詞P（v,w）定義了弧vv,w>的意義或信息}基木操作P:CreateGmph(&G,V,VR)初始條件：v是圖的頂點(diǎn)集，VR是圖

4、屮弧的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖G。DestroyGraph(&G)初始條件：圖G存在。操作結(jié)果：銷毀圖GLocateVex(G,u)初始條件：圖G存在，u和G屮定點(diǎn)有相同特征。操作結(jié)果：若圖G中存在頂點(diǎn)U,則返回頂點(diǎn)在圖中的位置：否則返回其他信息。GetVex(G,v)初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：返冋v的值tPutVex(&G,v,value)...初始條件：圖G存在。操作結(jié)果：對(duì)v賦值valueo2)存儲(chǔ)結(jié)構(gòu)typedefstmct{intbegin;intend;intweight;}edge;typedefstmct{in

5、tadj:intweight;}AdjMatrix[MAX][MAX];typedefstmct{AdjMatrixarc;intvexnum,arcnum;}MGraph:流程圖:輸入給定圖的邊數(shù)和頂點(diǎn)數(shù)該函數(shù)中主要有6段代碼，分別是圖的構(gòu)建代碼，對(duì)權(quán)值排序的代碼，交換權(quán)值代碼，最小生成數(shù)代碼，找尾代碼，主函數(shù)代碼。6段代碼分別實(shí)現(xiàn)不同的功能,共同滿足題目所需要求。4：調(diào)試與測(cè)驗(yàn)4.1：調(diào)試分析終于，在老師的耐心指導(dǎo)和同學(xué)的幫助匚我的課設(shè)任務(wù)完成了。通過(guò)這次課程設(shè)計(jì)屮遇到的許多問(wèn)題，我收獲頗多，下而就談一談我遇到的一個(gè)主要問(wèn)題及相應(yīng)的產(chǎn)生原因。問(wèn)題：頂點(diǎn)名的類

6、型識(shí)別.現(xiàn)象當(dāng)用字母表示頂點(diǎn)時(shí)，程序進(jìn)入死循環(huán)。原現(xiàn)頂點(diǎn)名稱與頂點(diǎn)數(shù)M于同一數(shù)據(jù)類型即足int整形，當(dāng)出現(xiàn)類型沖突時(shí)，程序不能識(shí)別就會(huì)發(fā)生沖突。4.2：測(cè)驗(yàn)1）事例524536656-

7、O

8、x

9、請(qǐng)輸入2與3N間的權(quán)值:5請(qǐng)輸入有邊的2個(gè)頂點(diǎn)25請(qǐng)輸入2與5之間的權(quán)值:3請(qǐng)輸入有邊的2個(gè)頂點(diǎn)53請(qǐng)輸入5與3之間的權(quán)值I右持］—&屯丁」2、［工點(diǎn)56請(qǐng)輸入5與6之間的權(quán)值:6情輸入有邊的2個(gè)頂點(diǎn)36請(qǐng)輸入3與6之間的權(quán)值：4請(qǐng)輸入有邊的2個(gè)頂點(diǎn)34請(qǐng)輸入3與4之間的權(quán)值：4請(qǐng)輸入有邊的2個(gè)頂點(diǎn)465>project設(shè)計(jì)總結(jié)通過(guò)這次試驗(yàn)更深刻的理解了什么是圖，怎么樣去

10、創(chuàng)造圖，利用圖來(lái)解決實(shí)際問(wèn)題,利用克魯斯卡爾算法去解決最小生成樹(shù)問(wèn)題。參考文獻(xiàn)《數(shù)據(jù)結(jié)構(gòu)（Ci吾言版）》嚴(yán)蔚敏吳偉民編著淸華人學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚皺》（教學(xué)視頻）《數(shù)據(jù)結(jié)構(gòu)鋅法實(shí)現(xiàn)及解析》髙一凡四安電子科技大學(xué)岀版社