普里姆算法求最小生成樹報(bào)告大學(xué)畢業(yè)論文.doc

ID:13668685

大小:4.36 MB

頁數(shù):35頁

時(shí)間:2018-07-23

普里姆算法求最小生成樹報(bào)告大學(xué)畢業(yè)論文.doc_第1頁
普里姆算法求最小生成樹報(bào)告大學(xué)畢業(yè)論文.doc_第2頁
普里姆算法求最小生成樹報(bào)告大學(xué)畢業(yè)論文.doc_第3頁
普里姆算法求最小生成樹報(bào)告大學(xué)畢業(yè)論文.doc_第4頁
普里姆算法求最小生成樹報(bào)告大學(xué)畢業(yè)論文.doc_第5頁
資源描述:

《普里姆算法求最小生成樹報(bào)告大學(xué)畢業(yè)論文.doc》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

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

2、__________________________________________________________________________成績(五級記分制):_____________________教師簽名:_____________________________目錄1需求分析11.1系統(tǒng)目標(biāo)11.2主體功能11.2開發(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鄰接矩陣

3、Output()輸出函數(shù)程序框圖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ǎng)圖鄰接矩陣存儲(chǔ)93.2.3創(chuàng)建有向網(wǎng)圖鄰接表存儲(chǔ)103.2.4創(chuàng)建無向網(wǎng)圖鄰接表存儲(chǔ)113.2.5prim算法求最小生成樹123.2.6輸出鄰接矩陣存儲(chǔ)函數(shù)133.2.7輸出鄰接表存儲(chǔ)函數(shù)143.2.8鄰接表轉(zhuǎn)換成鄰接矩陣函數(shù)144測試154.1調(diào)試準(zhǔn)備154.2調(diào)試結(jié)果165總結(jié)21參考文獻(xiàn)22附錄全部代碼231需求分析針對現(xiàn)實(shí)生活中,許多地方需要考慮到如:郵遞員送信,在n個(gè)城市之間建立通信網(wǎng)絡(luò)等最短路徑的

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

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

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

7、權(quán)圖,并能用Prim算法求該圖的最小生成樹,帶菜單提示,可以根據(jù)需求進(jìn)行選擇:如圖2.1所示。圖2.1主程序模塊圖332.2系統(tǒng)流程圖2.2.1CreateMGraph()函數(shù)程序框圖建立圖g的鄰接矩陣:圖的鄰接矩陣可利用兩個(gè)數(shù)組實(shí)現(xiàn),一個(gè)是一維數(shù)組,用來存儲(chǔ)圖中的頂點(diǎn)信息;另一個(gè)是二維數(shù)組,用來存儲(chǔ)圖中頂點(diǎn)之間的關(guān)系,該二維數(shù)組稱為鄰接矩陣。如圖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,因此該算法的

8、時(shí)間復(fù)雜度為O(n2),與網(wǎng)中的邊數(shù)無關(guān),因此普里姆算法適用于求邊稠密的最小生成樹。如圖2.3圖2.3prim函數(shù)332.2.3createALgraph()函數(shù)程序框圖定義整型

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

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

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