最小生成樹問題的算法實(shí)現(xiàn)及復(fù)雜度分析—天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院(算法設(shè)計(jì)與分析)-展示頁(yè)
2024-08-25 22:19本頁(yè)面
【正文】 ） 1. 頂點(diǎn)查找函數(shù)，因?yàn)轫旤c(diǎn)的值和數(shù)組位置的下標(biāo)不一定相等，所以加入頂點(diǎn)查找函數(shù)，返回頂點(diǎn)的值，便于結(jié)果顯示、區(qū)分指針與內(nèi)容，使思路更為清晰。int weight。typedef struct{VertexType head。}closedge [MAX_VERTEX_NUM]。typedef struct{VertexType adjvex。//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}MGraph。//頂點(diǎn)向量AdjMatrix arcs。}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。typedef int VRType。本程序采用的圖定義是無向圖的定義方式，存儲(chǔ)模塊采用鄰接矩陣，便于查找。typedef int VRType。define MAX_VERTEX_NUM 20//最大頂點(diǎn)數(shù)define QM 100//最大值define OK 1define ERROR 0int visited[MAX_VERTEX_NUM]。gt。lt。本程序可接受的最大頂點(diǎn)數(shù)為20個(gè)，沒有連接的點(diǎn)之間，用100表示其權(quán)值。由此，在普里姆算法中需要附設(shè)一個(gè)輔助數(shù)組 closedge，以記錄從集合 U 到集合 VU 中每個(gè)頂點(diǎn)當(dāng)前的權(quán)值最小邊。quot。quot。在一般情況下，假設(shè)圖 G=(V,E) 中已落在生成樹上的頂點(diǎn)集為U，則尚未落在生成樹上的頂點(diǎn)集為 VU，則從 (VU) 頂點(diǎn)集中選取加入生成樹的頂點(diǎn) w 應(yīng)滿足下列條件：它和生成樹上的頂點(diǎn)之間的邊上的權(quán)值是在聯(lián)接這兩類頂點(diǎn)的所有邊中權(quán)值屬最小。 正文 普里姆（Prim）算法思想普里姆算法則從另一個(gè)角度構(gòu)造連通網(wǎng)的最小生成樹。一棵生成樹的代價(jià)就是樹上各邊的代價(jià)之和。這個(gè)問題便是構(gòu)造連通網(wǎng)的最小代價(jià)生成樹（簡(jiǎn)稱最小生成樹）的問題。對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹，每一個(gè)生成樹都可以是一個(gè)通信網(wǎng)。這時(shí)，自然會(huì)考慮這樣一個(gè)問題，如何在節(jié)省費(fèi)用的前提下建立這個(gè)通信網(wǎng)？自然在每?jī)蓚€(gè)城市之間都可以設(shè)置一條線路，而這相應(yīng)的就要付出較高的經(jīng)濟(jì)代價(jià)。本設(shè)計(jì)以Visual Studio 2010作為開發(fā)平臺(tái)，C/C++語言作為編程語言，以鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)，編程實(shí)現(xiàn)了最小生成樹算法。而最小生成樹算法是算法設(shè)計(jì)與分析中的重要算法，最小生成樹也是最短路徑算法。最小生成樹問題的算法實(shí)現(xiàn)及復(fù)雜度分析—天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院(算法設(shè)計(jì)與分析) 算法設(shè)計(jì)與分析課程設(shè)計(jì)報(bào)告 學(xué)院計(jì)算機(jī)科學(xué)與技術(shù) 專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)年級(jí) 2011姓名學(xué)號(hào) 2013年5月19日 題目：最小生成樹問題的算法實(shí)現(xiàn)及復(fù)雜度分析 摘要：該程序操作簡(jiǎn)單，具有一定的應(yīng)用性。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)的算法理論基礎(chǔ)和軟件設(shè)計(jì)的技術(shù)基礎(chǔ)，在計(jì)算機(jī)領(lǐng)域中有著舉足輕重的作用，是計(jì)算機(jī)學(xué)科的核心課程。最短路徑的問題在現(xiàn)實(shí)生活中應(yīng)用非常廣泛，如郵遞員送信、公路造價(jià)等問題。構(gòu)造最小生成樹有很多算法， 引言：假設(shè)要在n個(gè)城市之間建立通信聯(lián)絡(luò)網(wǎng)，則連接n個(gè)城市只需要n1條線路。n個(gè)城市之間最多可以設(shè)置n（n1）/2條線路，那么如何在這些可能的線路中選擇n1 條使總的代價(jià)最小呢？可以用連通網(wǎng)來表示n 個(gè)城市以及n個(gè)城市之間可能設(shè)置的通信線路，其中網(wǎng)的頂點(diǎn)表示城市，邊表示兩個(gè)城市之間的線路，賦予邊的權(quán)值表示相應(yīng)的代價(jià)?，F(xiàn)在要選擇這樣一棵生成樹，也就是使總的代價(jià)最小。最小生成樹是指在所有生成樹中，邊上權(quán)值之和最小的生成樹，另外最小生成樹也可能是多個(gè)，他們之間的權(quán)值之和相等。而實(shí)現(xiàn)這個(gè)運(yùn)算的
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1