普里姆算法求最小生成樹課程設(shè)計(jì)報(bào)告-展示頁(yè)
2025-01-30 17:05本頁(yè)面
【正文】 始化鄰接矩陣*/ printf(輸入邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)的序號(hào)及權(quán)值：)。j++) { if(i==j) Gedges[i][j]=0。i++) for (j=0。 for (i=0。i++) scanf(\n%d,amp。 for (i=0。(Ge))。 scanf(%d,%d,amp。 printf(\t==有向網(wǎng)圖鄰接矩陣==\n)。 }graph。 edgetype edges[MaxVertexNum][MaxVertexNum]。(3) 鄰接表轉(zhuǎn)換成鄰接矩陣輔助結(jié)構(gòu)體typedef int edgetype 。 int n,e。typedef vertexnode AdjList[MaxVertexNum]。 edgenode *firstedges。 }edgenode。 int weight。(1) 鄰接表define MaxVertexNum 100typedef int vertextype。 int n,e。typedef struct{ VertexType vexs[MaxVertexNum]。 prim函數(shù) createALgraph()函數(shù)程序框圖定義整型i,j,k,w,輸入頂點(diǎn)數(shù)和邊數(shù)，執(zhí)行循環(huán)讀取頂點(diǎn)信息建立頂點(diǎn)表，將邊表置為空表，建立空表，輸入邊（vi,vj）上的頂點(diǎn)序號(hào)，向內(nèi)存申請(qǐng)空間生成表結(jié)點(diǎn)，將s的指針指向當(dāng)前頂點(diǎn)上指向的結(jié)點(diǎn)，后將當(dāng)前頂點(diǎn)的指針指向s, CreateALgraph()函數(shù)()輸出函數(shù)程序框圖定義兩個(gè)參數(shù)i，j，執(zhí)行循環(huán)將指向之前存儲(chǔ)到數(shù)組中的相關(guān)頂點(diǎn)和邊之間的關(guān)系然后打印輸出， 鄰接矩陣Output()輸出函數(shù)3 詳細(xì)設(shè)計(jì)定義鄰接矩陣鄰接表數(shù)據(jù)結(jié)構(gòu)define MaxVertexNum 100define max 1000typedef int VertexType。 主程序模塊圖 CreateMGraph()函數(shù)程序框圖建立圖g的鄰接矩陣：圖的鄰接矩陣可利用兩個(gè)數(shù)組實(shí)現(xiàn)，一個(gè)是一維數(shù)組，用來存儲(chǔ)圖中的頂點(diǎn)信息；另一個(gè)是二維數(shù)組，用來存儲(chǔ)圖中頂點(diǎn)之間的關(guān)系，該二維數(shù)組稱為鄰接矩陣。 用Visual C++，一是創(chuàng)建一個(gè)新的Viusal C++；二是在該項(xiàng)目中創(chuàng)建C程序文件，并編輯C語(yǔ)言程序。利用它不僅可以開發(fā)控制臺(tái)應(yīng)用程序，還可以開發(fā)Windows SDK、MFC等應(yīng)用程序。，并能夠用Prim算法求該網(wǎng)圖的最小生成樹。根據(jù)課程設(shè)計(jì)題目的相關(guān)要求，應(yīng)該完成以下目標(biāo)：，該網(wǎng)圖既能是無向網(wǎng)圖，有能是有向網(wǎng)圖；；。求圖的最小生成樹有很多實(shí)際應(yīng)用。在圖論中，常常將樹定義為一個(gè)無回路連通圖。 課程設(shè)計(jì)成果 學(xué)院: 計(jì)算機(jī)工程學(xué)院 班 級(jí): 計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)生姓名: 學(xué) 號(hào): 設(shè)計(jì)地點(diǎn)（單位）： 設(shè)計(jì)題目: 普里姆算法求最小生成樹 完成日期： 2016年 1月6日 指導(dǎo)教師評(píng)語(yǔ): __________________________________________________________________________________________________________________________________________________________________________________________ ________________________________________________________________________________成績(jī)(五級(jí)記分制):_____________________教師簽名:_____________________________ 目錄1 需求分析 1 1 1 12 概要設(shè)計(jì) 2 2 3 CreateMGraph()函數(shù)程序框圖 3 4 createALgraph()函數(shù)程序框圖 5()輸出函數(shù)程序框圖 53 詳細(xì)設(shè)計(jì) 6 6 8 8 9 10 11 prim算法求最小生成樹 12 13 14 144 測(cè)試 15 15 165 總結(jié) 21參考文獻(xiàn) 22附錄 全部代碼 23 1 需求分析針對(duì)現(xiàn)實(shí)生活中，許多地方需要考慮到如：郵遞員送信，在n個(gè)城市之間建立通信網(wǎng)絡(luò)等最短路徑的問題，本應(yīng)用程序正是基于這一現(xiàn)實(shí)問題，在vc++的平臺(tái)下，采用普里姆算法對(duì)此作出解決，本程序主要包含2大模塊，分別為采用鄰接矩陣（表）的存儲(chǔ)方式建立帶權(quán)的（有）無向網(wǎng)絡(luò)圖和利用普里姆算法對(duì)所建的網(wǎng)絡(luò)圖求最小代生成樹。它的最終目的是以最經(jīng)濟(jì)、最實(shí)惠、最節(jié)約的方式解決生活中的最短路徑問題，以求給人們提供更節(jié)約、更便利的生活。對(duì)于一個(gè)帶權(quán)的無向連通圖，其每個(gè)生成樹所有邊上的權(quán)值之和可能不同，我們把所有邊上權(quán)值之和最小的生成樹稱為圖的最小生成樹。例如，通訊線路鋪設(shè)造價(jià)最優(yōu)問題就是一個(gè)最小生成樹問題。，可以根據(jù)需求進(jìn)行選項(xiàng)：，且該網(wǎng)圖可能為有向圖也可能為無向圖，并采用鄰接表和鄰接矩陣（起點(diǎn)、終點(diǎn)和權(quán)值）兩種存儲(chǔ)結(jié)構(gòu)。操作系統(tǒng)：Windows編譯集成環(huán)境（IDE）：VC++ Visual C++（簡(jiǎn)稱VC++）是強(qiáng)大的C/C++軟件開發(fā)工具，使用非常廣泛，已經(jīng)成為程序員首選的開發(fā)工具。因?yàn)楸菊n題主要利用C語(yǔ)言描述普利姆算法生成最小生成樹，所以可以使用Visual C++。2 概要設(shè)計(jì)該程序可輸入的數(shù)據(jù)可為100以內(nèi)的整數(shù)；可建立帶權(quán)圖，并能用Prim算法求該圖的最小生成樹，帶菜單提示，可以根據(jù)需求進(jìn)行選擇：。 CreateMGraph()函數(shù)程序框圖33 普里姆算法中有多個(gè)循環(huán)，假設(shè)頂點(diǎn)的個(gè)數(shù)是n，則第一層循環(huán)的頻度為n1，第二層循環(huán)的頻度為n，因此該算法的時(shí)間復(fù)雜度為O（n2），與網(wǎng)中的邊數(shù)無關(guān)，因此普里姆算法適用于求邊稠密的最小生成樹。typedef int EdgeType。 EdgeType edges[MaxVertexNum][MaxVertexNum]。}MGraph。typedef struct node{ int adjvex。 struct node *next。typedef struct vnode{
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1