資源描述：
《普里姆算法求最小生成樹課程設(shè)計報告》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。
1、課程設(shè)計成果學(xué)院:計算機(jī)工程學(xué)院班級:計算機(jī)科學(xué)與技術(shù)學(xué)生姓名:學(xué)號:設(shè)計地點(diǎn)（單位）：設(shè)計題目:普里姆算法求最小生成樹完成日期：2016年1月6日指導(dǎo)教師評語:_______________________________________________________________________________________________________________________________________________________________________________________________________
2、___________________________________________________________________成績(五級記分制):_____________________教師簽名:_____________________________目錄1需求分析11.1系統(tǒng)目標(biāo)11.2主體功能11.2開發(fā)環(huán)境12概要設(shè)計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è)計63.1數(shù)據(jù)結(jié)構(gòu)63.2模塊設(shè)計83.2.1創(chuàng)建有向網(wǎng)圖鄰接矩陣存儲83.2.2創(chuàng)建無向網(wǎng)圖鄰接矩陣存儲93.2.3創(chuàng)建有向網(wǎng)圖鄰接表存儲103.2.4創(chuàng)建無向網(wǎng)圖鄰接表存儲113.2.5prim算法求最小生成樹123.2.6輸出鄰接矩陣存儲函數(shù)133.2.7輸出鄰接表存儲函數(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個城市之間建立通信網(wǎng)絡(luò)等最短路徑的問題，本應(yīng)用程序正是基于這一現(xiàn)實(shí)問題，在v
4、c++的平臺下，采用普里姆算法對此作出解決，本程序主要包含2大模塊，分別為采用鄰接矩陣（表）的存儲方式建立帶權(quán)的（有）無向網(wǎng)絡(luò)圖和利用普里姆算法對所建的網(wǎng)絡(luò)圖求最小代生成樹。它的最終目的是以最經(jīng)濟(jì)、最實(shí)惠、最節(jié)約的方式解決生活中的最短路徑問題，以求給人們提供更節(jié)約、更便利的生活。在圖論中，常常將樹定義為一個無回路連通圖。對于一個帶權(quán)的無向連通圖，其每個生成樹所有邊上的權(quán)值之和可能不同，我們把所有邊上權(quán)值之和最小的生成樹稱為圖的最小生成樹。求圖的最小生成樹有很多實(shí)際應(yīng)用。例如，通訊線路鋪設(shè)造價最優(yōu)問題就是一個最小生成樹問題。1.1系統(tǒng)目標(biāo)根據(jù)課程設(shè)計題目的
5、相關(guān)要求，應(yīng)該完成以下目標(biāo)：1.能夠先生成一個網(wǎng)圖，該網(wǎng)圖既能是無向網(wǎng)圖，有能是有向網(wǎng)圖；2.要求分別采用鄰接矩陣和鏈接表存儲來完成；3.最后打印輸出最小生成樹。1.2主體功能1.該程序會有菜單提示，可以根據(jù)需求進(jìn)行選項(xiàng)：2.能夠生成網(wǎng)圖并確定其存儲形式，且該網(wǎng)圖可能為有向圖也可能為無向圖，并采用鄰接表和鄰接矩陣（起點(diǎn)、終點(diǎn)和權(quán)值）兩種存儲結(jié)構(gòu)。3.可以建立帶權(quán)圖，并能夠用Prim算法求該網(wǎng)圖的最小生成樹。1.2開發(fā)環(huán)境操作系統(tǒng)：Windows編譯集成環(huán)境（IDE）：VC++6.0Visual33C++6.0（簡稱VC++6.0）是強(qiáng)大的C/C++軟件開
6、發(fā)工具，使用非常廣泛，已經(jīng)成為程序員首選的開發(fā)工具。利用它不僅可以開發(fā)控制臺應(yīng)用程序，還可以開發(fā)WindowsSDK、MFC等應(yīng)用程序。因?yàn)楸菊n題主要利用C語言描述普利姆算法生成最小生成樹，所以可以使用VisualC++6.0開發(fā)控制臺程序。用VisualC++6.0編寫C語言程序需要如下兩個步驟，一是創(chuàng)建一個新的ViusalC++6.0控制臺項(xiàng)目；二是在該項(xiàng)目中創(chuàng)建C程序文件，并編輯C語言程序。2概要設(shè)計2.1功能模塊劃分該程序可輸入的數(shù)據(jù)可為100以內(nèi)的整數(shù)；可建立帶權(quán)圖，并能用Prim算法求該圖的最小生成樹，帶菜單提示，可以根據(jù)需求進(jìn)行選擇：如圖2
7、.1所示。圖2.1主程序模塊圖332.2系統(tǒng)流程圖2.2.1CreateMGraph()函數(shù)程序框圖建立圖g的鄰接矩陣：圖的鄰接矩陣可利用兩個數(shù)組實(shí)現(xiàn)，一個是一維數(shù)組，用來存儲圖中的頂點(diǎn)信息；另一個是二維數(shù)組，用來存儲圖中頂點(diǎn)之間的關(guān)系，該二維數(shù)組稱為鄰接矩陣。如圖2.2所示圖2.2CreateMGraph()函數(shù)程序框圖332.2.2普利姆函數(shù)程序框圖普里姆算法中有多個循環(huán)，假設(shè)頂點(diǎn)的個數(shù)是n，則第一層循環(huán)的頻度為n-1，第二層循環(huán)的頻度為n，因此該算法的時間復(fù)雜度為O（n2），與網(wǎng)中的邊數(shù)無關(guān)，因此普里姆算法適用于求邊稠密的最小生成樹。如圖2.3圖2
8、.3prim函數(shù)332.2.3createALgraph()函數(shù)程序框圖定義整型
