最小生成樹問題的算法實(shí)現(xiàn)及復(fù)雜度分析—天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院(算法設(shè)計(jì)與分析-展示頁
2024-11-28 06:51本頁面
【正文】 ， C/C++語言作為編程語言，以鄰接矩陣作為存儲結(jié)構(gòu)，編程實(shí)現(xiàn)了最小生成樹算法。而最小生成樹算法是算法 設(shè)計(jì)與分析中的重要算法，最小生成樹也是最短路徑算法。— 天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 (算法設(shè)計(jì)與分析 ) 算法設(shè)計(jì)與分析課程設(shè)計(jì)報(bào)告 學(xué)院計(jì)算機(jī)科學(xué)與技術(shù) 專業(yè)計(jì)算機(jī)科學(xué)與技術(shù) 年級 2020 姓名學(xué)號 2020年 5月 19日 題目：最小生成樹問題的算法實(shí)現(xiàn)及復(fù)雜度分析 摘要：該程序操作簡單，具有一定的應(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à)。現(xiàn)在要選擇這樣一棵生成樹，也就是使總的代價(jià)最小。最小生成樹是指在所有生成樹中，邊上權(quán)值之和最小的生成樹，另外最小生成樹也可能 是多個(gè)，他們之間的權(quán)值之和相等。而實(shí)現(xiàn)這個(gè)運(yùn)算的經(jīng)典算法就是普利姆算法。它的基本思想是：首先選取圖中任意一個(gè)頂點(diǎn) v 作為生成樹的根，之后繼續(xù)往生成樹中添加頂點(diǎn) w，則在頂點(diǎn) w 和頂點(diǎn) v 之間必須有邊，且該邊上的權(quán)值應(yīng)在所有和 v 相鄰接的邊中屬最小。 從 上述生成樹的構(gòu)造過程中回還可以發(fā)現(xiàn)一點(diǎn)，即每個(gè)頂點(diǎn)都是通過 一條邊 加入到生成樹上的，因此對集合 VU 中的每個(gè)頂點(diǎn)，當(dāng)它和集合 U 中的頂點(diǎn)有一條以上的邊相連時(shí)，只需要保留一條權(quán)值最小的邊即可。 普里姆算法構(gòu)造最 小生成樹的過程 普里姆（ Prim）算法設(shè)計(jì)： 一：定義模塊： 1. 頭文件、新類型及固定值定義。 includeiostream using namespace std。 typedef int VertexType。 2. 首先設(shè)計(jì)圖的存儲模塊，即定義類型。 typedef int VertexType。 typedef struct ArcCell//鄰接矩陣的值 { int adj。 typedef struct { VertexType vexs[MAX_VERTEX_NUM]。//鄰接矩陣 int vexnum,arum。 3. 在實(shí)現(xiàn)最小生成樹算法時(shí)，定義輔助數(shù)組，進(jìn)行判斷遍歷。 VRType lowcost。 4. 最后生成最小生成樹時(shí)，采用輔助數(shù)組進(jìn)行結(jié)果的記錄。 VRType last。 }result[MAX_VERTEX_NUM]。 int LocateVex(MGraph amp。 for(k=0。k++) {
法律信息相關(guān)推薦
鄂ICP備17016276號-1