最小生成樹(shù)問(wèn)題的算法實(shí)現(xiàn)及復(fù)雜度分析

1、算法設(shè)計(jì)與分析課程設(shè)計(jì)報(bào)告學(xué) 院計(jì)算機(jī)科學(xué)與技術(shù)專 業(yè)計(jì)算機(jī)科學(xué)與技術(shù)年 級(jí)姓 名 XXX學(xué) 號(hào)2013年5月19日題目：一心I :最小生成樹(shù)問(wèn)題的算法實(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é)科的核心課程。而最小生成樹(shù)算法是算法設(shè)計(jì)與分析中的重要算法，最 小生成樹(shù)也是最短路徑算法。最短路徑的問(wèn)題在現(xiàn)實(shí)生活中應(yīng)用非常廣泛，如郵 遞員送信、公路造價(jià)等問(wèn)題。本設(shè)計(jì)以Visual Studio 2010作為開(kāi)發(fā)平臺(tái)，C/C+ 語(yǔ)言作為編程語(yǔ)言，以鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)，編程實(shí)現(xiàn)了最小

2、生成樹(shù)算法。構(gòu) 造最小生成樹(shù)有很多算法，本文主要介紹了圖的概念、圖的遍歷，并分析了 PRIM 經(jīng)典算法的算法思想，最后用這種經(jīng)典算法實(shí)現(xiàn)了最小生成樹(shù)的生成。引言：丁 口：假設(shè)要在n個(gè)城市之間建立通信聯(lián)絡(luò)網(wǎng)，則連接n個(gè)城市只需要n-1 條線路。這時(shí)，自然會(huì)考慮這樣一個(gè)問(wèn)題，如何在節(jié)省費(fèi)用的前提下建立這個(gè)通 信網(wǎng)？自然在每?jī)蓚€(gè)城市之間都可以設(shè)置一條線路，而這相應(yīng)的就要付出較高的 經(jīng)濟(jì)代價(jià)。n個(gè)城市之間最多可以設(shè)置n（n-1）/2條線路，那么如何在這些可 能的線路中選擇n-1條使總的代價(jià)最小呢？可以用連通網(wǎng)來(lái)表示n個(gè)城市以及 n個(gè)城市之間可能設(shè)置的通信線路，其中網(wǎng)的頂點(diǎn)表示城市，邊表示兩個(gè)城市之 間

3、的線路，賦予邊的權(quán)值表示相應(yīng)的代價(jià)。對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多 不同的生成樹(shù)，每一個(gè)生成樹(shù)都可以是一個(gè)通信網(wǎng)?，F(xiàn)在要選擇這樣一棵生成樹(shù)， 也就是使總的代價(jià)最小。這個(gè)問(wèn)題便是構(gòu)造連通網(wǎng)的最小代價(jià)生成樹(shù)（簡(jiǎn)稱最小 生成樹(shù)）的問(wèn)題。最小生成樹(shù)是指在所有生成樹(shù)中，邊上權(quán)值之和最小的生成樹(shù)， 另外最小生成樹(shù)也可能是多個(gè)，他們之間的權(quán)值之和相等。一棵生成樹(shù)的代價(jià)就 是樹(shù)上各邊的代價(jià)之和。而實(shí)現(xiàn)這個(gè)運(yùn)算的經(jīng)典算法就是普利姆算法。正文普里姆(Prim )算法思想普里姆算法則從另一個(gè)角度構(gòu)造連通網(wǎng)的最小生成樹(shù)。它的基本思想是： 首先選取圖中任意一個(gè)頂點(diǎn)V作為生成樹(shù)的根，之后繼續(xù)往生成樹(shù)中添加頂點(diǎn) w，則在

4、頂點(diǎn)w和頂點(diǎn)V之間必須有邊，且該邊上的權(quán)值應(yīng)在所有和V相鄰接 的邊中屬最小。在一般情況下，假設(shè)圖G=(V,E)中已落在生成樹(shù)上的頂點(diǎn)集為 U，則尚未落在生成樹(shù)上的頂點(diǎn)集為V-U，則從(V-U)頂點(diǎn)集中選取加入生成樹(shù) 的頂點(diǎn)w應(yīng)滿足下列條件：它和生成樹(shù)上的頂點(diǎn)之間的邊上的權(quán)值是在聯(lián)接這 兩類頂點(diǎn)的所有邊中權(quán)值屬最小。從上述生成樹(shù)的構(gòu)造過(guò)程中回還可以發(fā)現(xiàn)一點(diǎn)，即每個(gè)頂點(diǎn)都是通過(guò)一 條邊加入到生成樹(shù)上的，因此對(duì)集合V-U中的每個(gè)頂點(diǎn)，當(dāng)它和集合U中的 頂點(diǎn)有一條以上的邊相連時(shí)，只需要保留一條權(quán)值最小的邊即可。由此，在普里 姆算法中需要附設(shè)一個(gè)輔助數(shù)組closedge，以記錄從集合U到集合V-U中每

5、個(gè)頂點(diǎn)當(dāng)前的權(quán)值最小邊。WS普里姆算法構(gòu)造最小生成樹(shù)的過(guò)程普里姆(Prim)算法設(shè)計(jì)：一：定義模塊：頭文件、新類型及固定值定義。本程序可接受的最大頂點(diǎn)數(shù)為20個(gè)，沒(méi)有連 接的點(diǎn)之間，用100表示其權(quán)值。#includeusing namespace std;#define MAX_VERTEX_NUM 20dj=QM;cout輸出網(wǎng)的個(gè)頂點(diǎn)(限數(shù)字)：endl;for(i=0;ii;cout建立弧，請(qǐng)輸入條弧的頂點(diǎn)和權(quán)值 (v1,v2,w):endl;for(k=0;kv1v2weight;i=LocateVex(G,v1);j=LocateVex(G,v2);if(i0|j0)return

6、ERROR;j.adj=weight;ji.adj=ij.adj;return OK;1.最小生成樹(shù)建立主程序，采用借助輔助數(shù)組的方式，對(duì)于輔助的數(shù)組，以 鄰接表的選擇點(diǎn)加入該數(shù)組，然后查找數(shù)組中權(quán)值最小，且未被選中的頂 點(diǎn)，然后返回該邊，加入最小生成樹(shù)中。void MiniSpanTree_PRIM(MGraph G,VertexType u)(closedge dge;owcost=kj.adj;djvex=u;owcost=0;djvex k endl;ead=dgek.adjvex;paxtime.last=k;x=LocateVex(G,dgek.adjvex);y=LocateVe

7、x(G,k);paxtime.weight=xy.adj;time+;dgek.lowcost=0;djdgej.lowcost)(owcost=kj.adj;dgej.adjvex=k;eadpaxtime.last paxtime.weightendl;輔助生成最小生成樹(shù)的函數(shù)。int minimun(MGraph G,closedge F)(int i,min;for(i=0;i;i+)if(Fi.lowcost!=0) break;min=i;for(i=0;i;i+)if(Fi.lowcost!=0 &Fi.lowcostFmin.lowcost) min=i;return min;

8、數(shù)組的樣式:jLowcostadjvex過(guò)程如下表：頂點(diǎn)標(biāo)號(hào)都比圖中的小1，比如v1為0，v2為1，這里首先選 擇v1點(diǎn)。j012345Lowcost0423100100adjvex111111從這個(gè)表格可以看到依附到v1頂點(diǎn)的v3的Lowcost最小為2,那么選擇v3， 選擇了之后我們必須要更新Lowcost數(shù)組的值，因?yàn)橛涗洀腢到VU具有最小 代價(jià)的邊，加入之后就會(huì)改變。新加入的點(diǎn)到其他各點(diǎn)的權(quán)值比原來(lái)的權(quán)值更小， 則替換！采取遍歷的方法！j012345Lowcost04011002adjvex111416Lowcost = 0為我們已經(jīng)選出來(lái)的頂點(diǎn)，接著繼續(xù)在Lowcost中選出值不為

9、0的最小值，作為下一個(gè)最小生成樹(shù)的點(diǎn)。這樣一直選擇下去直到選出所有的頂點(diǎn)。最小生成樹(shù)建立，那么需要借用輔助數(shù)組，進(jìn)行記錄。int minimun(MGraph G,closedge F)(int i,min;for(i=0;i;i+)if(Fi.lowcost!=0) break;min=i;for(i=0;i;i+)if(Fi.lowcost!=0 &Fi.lowcostFmin.lowcost) min=i;return min;調(diào)試時(shí)，加入的函數(shù)，輸出鄰接矩陣和輔助數(shù)組，進(jìn)行查看和判斷正誤。void PrintMatrix(MGraph &G)dj!=QM)coutij.adj”;els

10、e cout8 ;coutendl;void printclosedge(MGraph G,closedge X) owcost;coutendladjvex:；for(i=0;i;i+)cout Xi.adjvex;主程序。void main()(MGraph G;VertexType u;=0;CreateUDN(G);PrintMatrix(G);coutu;MiniSpanTree_PRIM(G,u);system(pause);普里姆(Prim)算法分析：Prim算法的時(shí)間復(fù)雜度主要是在雙重循環(huán)構(gòu)造最小生成樹(shù)的過(guò)程中，設(shè)圖 的頂點(diǎn)數(shù)為山則雙重循環(huán)的時(shí)間復(fù)雜度為O(n2)，在生成最小生

11、成樹(shù)的過(guò)程中， 增加了兩個(gè)數(shù)組，closedge口和result 口數(shù)組，用來(lái)記錄所選頂點(diǎn)的全趨結(jié)點(diǎn)， 故空間復(fù)雜度為O(2n)。普里姆算法的時(shí)間復(fù)雜度與邊數(shù)e無(wú)關(guān)，該算法更適合 于求邊數(shù)較多的帶權(quán)無(wú)向連通圖的最小生成樹(shù)。普里姆(Prim)算法實(shí)驗(yàn)結(jié)果:采用的數(shù)據(jù)：6 112 3 4 5 62 41 4 33 25 34 43 54 16 25 66 26 41實(shí)驗(yàn)結(jié)果:D:Usersluo yiwenDesktoptesttest請(qǐng)輸A蔓始的點(diǎn)d卵規(guī)成直為:i： 0 1 2 3 4 5loucost: 0423 100 100adjvex： 111111K的尋求結(jié)果為數(shù)組頓中的下標(biāo)）:2 捕

12、尋求結(jié)果為數(shù)組頓中的下標(biāo)）:3 3 4K的尋求結(jié)果為數(shù)組頓中的下標(biāo)）：5K的尋求結(jié)果為（數(shù)組dg中的下標(biāo)）:1H的尋求結(jié)果為（數(shù)組&我中的下標(biāo)）:42 53 1 六.,時(shí) 權(quán)值3 1 六.,時(shí) 權(quán)值132411324162124請(qǐng)矗專鍵A-圖表分析:(b)(a)(b)(a)(f)(f)結(jié)論與展望：運(yùn)用prim算法構(gòu)造圖的最小生成樹(shù)，使生成樹(shù)的權(quán)值和達(dá)到最小，即耗費(fèi)最小， 這里選擇貪心策略，從一個(gè)頂點(diǎn)出發(fā)，選擇到剩余頂點(diǎn)的邊權(quán)值最小的頂點(diǎn)，將 之并入到所夠造的生成樹(shù)之中，同時(shí)修改剩下的頂點(diǎn)到生成 樹(shù)的權(quán)值，再?gòu)氖?余頂點(diǎn)中繼續(xù)選擇到生成樹(shù)耗費(fèi)最小的頂點(diǎn)，繼續(xù)并入該頂點(diǎn)，直到所有的頂點(diǎn) 全部并入到生成樹(shù)中為止，其核心思想在于不斷地在剩余頂點(diǎn)中選取到生成樹(shù) 耗費(fèi)最小的頂點(diǎn)，將之并入后，修改剩余頂點(diǎn)到生成樹(shù)相應(yīng)的權(quán)值