普里姆算法求最小生成樹(shù)課程設(shè)計(jì)報(bào)告

ID:25087632

大?。?.36 MB

頁(yè)數(shù):35頁(yè)

時(shí)間:2018-11-17

普里姆算法求最小生成樹(shù)課程設(shè)計(jì)報(bào)告_第1頁(yè)
普里姆算法求最小生成樹(shù)課程設(shè)計(jì)報(bào)告_第2頁(yè)
普里姆算法求最小生成樹(shù)課程設(shè)計(jì)報(bào)告_第3頁(yè)
普里姆算法求最小生成樹(shù)課程設(shè)計(jì)報(bào)告_第4頁(yè)
普里姆算法求最小生成樹(shù)課程設(shè)計(jì)報(bào)告_第5頁(yè)
資源描述:

《普里姆算法求最小生成樹(shù)課程設(shè)計(jì)報(bào)告》由會(huì)員上傳分享,免費(fèi)在線(xiàn)閱讀,更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)

1、課程設(shè)計(jì)成果學(xué)院:計(jì)算機(jī)工程學(xué)院班級(jí):計(jì)算機(jī)科學(xué)與技術(shù)學(xué)生姓名:學(xué)號(hào):設(shè)計(jì)地點(diǎn)(單位):設(shè)計(jì)題目:普里姆算法求最小生成樹(shù)完成日期:2016年1月6日指導(dǎo)教師評(píng)語(yǔ):_______________________________________________________________________________________________________________________________________________________________________________________________________

2、___________________________________________________________________成績(jī)(五級(jí)記分制):_____________________教師簽名:_____________________________目錄1需求分析11.1系統(tǒng)目標(biāo)11.2主體功能11.2開(kāi)發(fā)環(huán)境12概要設(shè)計(jì)22.1功能模塊劃分22.2系統(tǒng)流程圖32.2.1CreateMGraph()函數(shù)程序框圖32.2.2普利姆函數(shù)程序框圖42.2.3createALgraph()函數(shù)程序框圖52.2.4鄰接矩陣Output()輸出函數(shù)程序

3、框圖53詳細(xì)設(shè)計(jì)63.1數(shù)據(jù)結(jié)構(gòu)63.2模塊設(shè)計(jì)83.2.1創(chuàng)建有向網(wǎng)圖鄰接矩陣存儲(chǔ)83.2.2創(chuàng)建無(wú)向網(wǎng)圖鄰接矩陣存儲(chǔ)93.2.3創(chuàng)建有向網(wǎng)圖鄰接表存儲(chǔ)103.2.4創(chuàng)建無(wú)向網(wǎng)圖鄰接表存儲(chǔ)113.2.5prim算法求最小生成樹(shù)123.2.6輸出鄰接矩陣存儲(chǔ)函數(shù)133.2.7輸出鄰接表存儲(chǔ)函數(shù)143.2.8鄰接表轉(zhuǎn)換成鄰接矩陣函數(shù)144測(cè)試154.1調(diào)試準(zhǔn)備154.2調(diào)試結(jié)果165總結(jié)21參考文獻(xiàn)22附錄全部代碼231需求分析針對(duì)現(xiàn)實(shí)生活中,許多地方需要考慮到如:郵遞員送信,在n個(gè)城市之間建立通信網(wǎng)絡(luò)等最短路徑的問(wèn)題,本應(yīng)用程序正是基于這一現(xiàn)實(shí)問(wèn)題,在v

4、c++的平臺(tái)下,采用普里姆算法對(duì)此作出解決,本程序主要包含2大模塊,分別為采用鄰接矩陣(表)的存儲(chǔ)方式建立帶權(quán)的(有)無(wú)向網(wǎng)絡(luò)圖和利用普里姆算法對(duì)所建的網(wǎng)絡(luò)圖求最小代生成樹(shù)。它的最終目的是以最經(jīng)濟(jì)、最實(shí)惠、最節(jié)約的方式解決生活中的最短路徑問(wèn)題,以求給人們提供更節(jié)約、更便利的生活。在圖論中,常常將樹(shù)定義為一個(gè)無(wú)回路連通圖。對(duì)于一個(gè)帶權(quán)的無(wú)向連通圖,其每個(gè)生成樹(shù)所有邊上的權(quán)值之和可能不同,我們把所有邊上權(quán)值之和最小的生成樹(shù)稱(chēng)為圖的最小生成樹(shù)。求圖的最小生成樹(shù)有很多實(shí)際應(yīng)用。例如,通訊線(xiàn)路鋪設(shè)造價(jià)最優(yōu)問(wèn)題就是一個(gè)最小生成樹(shù)問(wèn)題。1.1系統(tǒng)目標(biāo)根據(jù)課程設(shè)計(jì)題目的

5、相關(guān)要求,應(yīng)該完成以下目標(biāo):1.能夠先生成一個(gè)網(wǎng)圖,該網(wǎng)圖既能是無(wú)向網(wǎng)圖,有能是有向網(wǎng)圖;2.要求分別采用鄰接矩陣和鏈接表存儲(chǔ)來(lái)完成;3.最后打印輸出最小生成樹(shù)。1.2主體功能1.該程序會(huì)有菜單提示,可以根據(jù)需求進(jìn)行選項(xiàng):2.能夠生成網(wǎng)圖并確定其存儲(chǔ)形式,且該網(wǎng)圖可能為有向圖也可能為無(wú)向圖,并采用鄰接表和鄰接矩陣(起點(diǎn)、終點(diǎn)和權(quán)值)兩種存儲(chǔ)結(jié)構(gòu)。3.可以建立帶權(quán)圖,并能夠用Prim算法求該網(wǎng)圖的最小生成樹(shù)。1.2開(kāi)發(fā)環(huán)境操作系統(tǒng):Windows編譯集成環(huán)境(IDE):VC++6.0Visual33C++6.0(簡(jiǎn)稱(chēng)VC++6.0)是強(qiáng)大的C/C++軟件開(kāi)

6、發(fā)工具,使用非常廣泛,已經(jīng)成為程序員首選的開(kāi)發(fā)工具。利用它不僅可以開(kāi)發(fā)控制臺(tái)應(yīng)用程序,還可以開(kāi)發(fā)WindowsSDK、MFC等應(yīng)用程序。因?yàn)楸菊n題主要利用C語(yǔ)言描述普利姆算法生成最小生成樹(shù),所以可以使用VisualC++6.0開(kāi)發(fā)控制臺(tái)程序。用VisualC++6.0編寫(xiě)C語(yǔ)言程序需要如下兩個(gè)步驟,一是創(chuàng)建一個(gè)新的ViusalC++6.0控制臺(tái)項(xiàng)目;二是在該項(xiàng)目中創(chuàng)建C程序文件,并編輯C語(yǔ)言程序。2概要設(shè)計(jì)2.1功能模塊劃分該程序可輸入的數(shù)據(jù)可為100以?xún)?nèi)的整數(shù);可建立帶權(quán)圖,并能用Prim算法求該圖的最小生成樹(shù),帶菜單提示,可以根據(jù)需求進(jìn)行選擇:如圖2

7、.1所示。圖2.1主程序模塊圖332.2系統(tǒng)流程圖2.2.1CreateMGraph()函數(shù)程序框圖建立圖g的鄰接矩陣:圖的鄰接矩陣可利用兩個(gè)數(shù)組實(shí)現(xiàn),一個(gè)是一維數(shù)組,用來(lái)存儲(chǔ)圖中的頂點(diǎn)信息;另一個(gè)是二維數(shù)組,用來(lái)存儲(chǔ)圖中頂點(diǎn)之間的關(guān)系,該二維數(shù)組稱(chēng)為鄰接矩陣。如圖2.2所示圖2.2CreateMGraph()函數(shù)程序框圖332.2.2普利姆函數(shù)程序框圖普里姆算法中有多個(gè)循環(huán),假設(shè)頂點(diǎn)的個(gè)數(shù)是n,則第一層循環(huán)的頻度為n-1,第二層循環(huán)的頻度為n,因此該算法的時(shí)間復(fù)雜度為O(n2),與網(wǎng)中的邊數(shù)無(wú)關(guān),因此普里姆算法適用于求邊稠密的最小生成樹(shù)。如圖2.3圖2

8、.3prim函數(shù)332.2.3createALgraph()函數(shù)程序框圖定義整型

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫(huà)的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無(wú)此問(wèn)題,請(qǐng)放心下載。
2. 本文檔由用戶(hù)上傳,版權(quán)歸屬用戶(hù),天天文庫(kù)負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無(wú)法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶(hù)請(qǐng)聯(lián)系客服處理。
关闭