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

1、算法設(shè)計與分析課程設(shè)計報告學(xué) 院計算機科學(xué)與技術(shù)專 業(yè)計算機科學(xué)與技術(shù)年 級姓 名 XXX學(xué) 號2013年5月19日題目：一心I :最小生成樹問題的算法實現(xiàn)及復(fù)雜度分析 摘要：該程序操作簡單，具有一定的應(yīng)用性。數(shù)據(jù)結(jié)構(gòu)是計算機科學(xué)的算 法理論基礎(chǔ)和軟件設(shè)計的技術(shù)基礎(chǔ)，在計算機領(lǐng)域中有著舉足輕重的作用，是計 算機學(xué)科的核心課程。而最小生成樹算法是算法設(shè)計與分析中的重要算法，最 小生成樹也是最短路徑算法。最短路徑的問題在現(xiàn)實生活中應(yīng)用非常廣泛，如郵 遞員送信、公路造價等問題。本設(shè)計以Visual Studio 2010作為開發(fā)平臺，C/C+ 語言作為編程語言，以鄰接矩陣作為存儲結(jié)構(gòu)，編程實現(xiàn)了最小

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

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

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

5、個頂點當(dāng)前的權(quán)值最小邊。WS普里姆算法構(gòu)造最小生成樹的過程普里姆(Prim)算法設(shè)計：一：定義模塊：頭文件、新類型及固定值定義。本程序可接受的最大頂點數(shù)為20個，沒有連 接的點之間，用100表示其權(quán)值。#includeusing namespace std;#define MAX_VERTEX_NUM 20dj=QM;cout輸出網(wǎng)的個頂點(限數(shù)字)：endl;for(i=0;ii;cout建立弧，請輸入條弧的頂點和權(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ù)組，以 鄰接表的選擇點加入該數(shù)組，然后查找數(shù)組中權(quán)值最小，且未被選中的頂 點，然后返回該邊，加入最小生成樹中。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ù)。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過程如下表：頂點標(biāo)號都比圖中的小1，比如v1為0，v2為1，這里首先選 擇v1點。j012345Lowcost0423100100adjvex111111從這個表格可以看到依附到v1頂點的v3的Lowcost最小為2,那么選擇v3， 選擇了之后我們必須要更新Lowcost數(shù)組的值，因為記錄從U到VU具有最小 代價的邊，加入之后就會改變。新加入的點到其他各點的權(quán)值比原來的權(quán)值更小， 則替換！采取遍歷的方法！j012345Lowcost04011002adjvex111416Lowcost = 0為我們已經(jīng)選出來的頂點，接著繼續(xù)在Lowcost中選出值不為

9、0的最小值，作為下一個最小生成樹的點。這樣一直選擇下去直到選出所有的頂點。最小生成樹建立，那么需要借用輔助數(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ù)組，進(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算法的時間復(fù)雜度主要是在雙重循環(huán)構(gòu)造最小生成樹的過程中，設(shè)圖 的頂點數(shù)為山則雙重循環(huán)的時間復(fù)雜度為O(n2)，在生成最小生

11、成樹的過程中， 增加了兩個數(shù)組，closedge口和result 口數(shù)組，用來記錄所選頂點的全趨結(jié)點， 故空間復(fù)雜度為O(2n)。普里姆算法的時間復(fù)雜度與邊數(shù)e無關(guān)，該算法更適合 于求邊數(shù)較多的帶權(quán)無向連通圖的最小生成樹。普里姆(Prim)算法實驗結(jié)果:采用的數(shù)據(jù)：6 112 3 4 5 62 41 4 33 25 34 43 54 16 25 66 26 41實驗結(jié)果:D:Usersluo yiwenDesktoptesttest請輸A蔓始的點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 六.,時 權(quán)值3 1 六.,時 權(quán)值132411324162124請矗專鍵A-圖表分析:(b)(a)(b)(a)(f)(f)結(jié)論與展望：運用prim算法構(gòu)造圖的最小生成樹，使生成樹的權(quán)值和達(dá)到最小，即耗費最小， 這里選擇貪心策略，從一個頂點出發(fā)，選擇到剩余頂點的邊權(quán)值最小的頂點，將 之并入到所夠造的生成樹之中，同時修改剩下的頂點到生成 樹的權(quán)值，再從剩 余頂點中繼續(xù)選擇到生成樹耗費最小的頂點，繼續(xù)并入該頂點，直到所有的頂點 全部并入到生成樹中為止，其核心思想在于不斷地在剩余頂點中選取到生成樹 耗費最小的頂點，將之并入后，修改剩余頂點到生成樹相應(yīng)的權(quán)值