Prim算法和Kruskal算法的Matlab實現(xiàn)

1、計算機仿真期末大作業(yè)Prim算法和Kruskal算法的Matlab實現(xiàn)05605劉禹050697（30）連線問題應(yīng)用舉例：欲鋪設(shè)連接個城市的高速公路，若城與城之間的高速公路造價為，試設(shè)計一個線路圖，使總的造價最低。連線問題的數(shù)學(xué)模型就是圖論中在連通的賦權(quán)圖上求權(quán)最小的支撐樹。試用Matlab分別實現(xiàn)求最小支撐數(shù)的Prim算法和Krusal算法（避圈法）。一.基本要求：（1） 畫出程序流程圖；（2） 對關(guān)鍵算法、變量和步驟進行解釋說明；（3） 用如下兩圖對所寫算法的正確性進行驗證。即輸入圖的信息，輸出對應(yīng)圖的最小支撐樹及其權(quán)值。 （4）分析兩種算法的實現(xiàn)復(fù)雜度。二.擴展要求：（1）提供對算法效率

2、（復(fù)雜度）進行評估的方法，并通過舉例驗證，與分析得到的算法復(fù)雜度結(jié)果相對照；（2）從降低內(nèi)存消耗、減少計算時間的角度，對算法進行優(yōu)化。三實驗步驟I.用Prim算法求最小生成樹i算法分析及需求分析，程序設(shè)計prim算法的基本思想是：設(shè)G=（V，E）是一個無向連通網(wǎng)，令T=（U，TE）是G的最小生成樹。T的初始狀態(tài)為U=v0（v0V）TE=，然后重復(fù)執(zhí)行下述操作：在所有uU，vV-U的邊中找一條代價最小的邊（u，v）并入集合TE，同時v并入U，直至U=V為止。顯然，Prim算法的基本思想是以局部最優(yōu)化謀求全局的最優(yōu)化，而且，還涉及到起始結(jié)點的問題。本程序完成的功能是：從圖中的任意結(jié)點出發(fā)，都能夠找

3、出最小生成樹實現(xiàn)方案分析：Prim算法的關(guān)鍵是如何找到連接U和V-U的最短邊來擴充生成樹T。設(shè)當前T中有k個點（即T的頂點集U中有k個頂點）則所有滿足uU，vV-U的邊最多有k×(n-k)條，從如此大的邊集中選取最短邊是不太經(jīng)濟的。利用MST性質(zhì)，可以用下述方法構(gòu)造候選最小邊集：對應(yīng)V-U中的每個頂點，保留從該頂點到U中的各頂點的最短邊，取候選邊最短邊集為V-U中的n-k個頂點所關(guān)聯(lián)的n-k條最短邊的集合。為表示候選最短邊集，需設(shè)置兩個一維數(shù)組lowcostn和adjvexn,其中l(wèi)owcost用來保存集合V-U中的各頂點與集合U中頂點的最短邊的權(quán)值，lowcostv=0表示頂點v已

4、經(jīng)加入最小生成樹中；adjvex用來保存依附于該邊在集合U中的頂點。例如下式表明頂點vi和頂點vk之間的權(quán)值為wlowcosti=w;adjvexi=k;程序流程圖關(guān)鍵代碼說明：1 將用于驗證算法正確性的兩幅圖用鄰接矩陣的形式保存，分別保存為文件Graph1.m,Graph2.m（注：矩陣的對角線元素設(shè)置為零。）并在主程序finallyprim中直接進行調(diào)用。2 在輸入起點時應(yīng)該給程序的閱讀者就該圖的頂點數(shù)作出提示，不然的話使用者很可能會輸入越界下標。采取的方法如下len=length(graph_adjacent);%求圖中有多少個頂點k=sprintf('please input

5、the point where you want to start ,do remember it must be between 1 and %d ',len);start_point=input(k);%輸入最小生成樹產(chǎn)生起點采取了sprintf格式化字符串的方法，就避免了編程的人每次根據(jù)輸入圖的頂點數(shù)手動對提示作修改。效果如下：在對第一幅圖進行算法驗證時在workspace會如下輸出:please input the point where you want to start ,do remember it must be between 1 and 7在對第二幅圖進行算法驗證時

6、在workspace會有如下輸出：please input the point where you want to start ,do remember it must be between 1 and 83 在輸出結(jié)果時為了使結(jié)果在workspace中輸出的清晰，使人一目了然，也使用了sprintf格式化字符串的方法，代碼如下s=0;for ii=1:len-1 k=sprintf('最小生成樹第%d條邊：（%d,%d），權(quán)值為%d',ii,tree(ii,1),tree(ii,2),graph_adjacent(tree(ii,1),tree(ii,2); disp(k);

7、 disp(' '); s=s+graph_adjacent(tree(ii,1),tree(ii,2); enddisp('最小生成樹的總代價為：')disp(s);4 下面對算法的核心部分進行說明：在len-1次循環(huán)中，每次循環(huán)要完成以下三項工作1.找到最小邊，（需要求lowcost數(shù)組的最小非零值，因為0表示該邊已經(jīng)被加入到了最小生成樹中）由于是求非零的最小值，就不能在直接用min函數(shù)了。我采取的方法是這樣的：k=lowcost>0;%k為一邏輯數(shù)組，它和lowcost同維，對于每一個位%置i如果lowcost(i)>0則k(i)=1 %否則k

8、(i)=0;稍候?qū)⒂眠@個數(shù)組進行輔助尋址cost_min=min(lowcost(k);%找出lowcost中除0外的最小值index=find(lowcost=cost_min);%找出此最小值在lowcost中的下標，即找到相應(yīng)的節(jié)點index=index(1);%因為最小值的下標可能不止一個，這里取第一個下標進行處理lowcost(index)=0;%表明該節(jié)點已經(jīng)加入了最小生成樹中采用這種方法不僅充分利用了matlab的built_in函數(shù)，還避免了自己編寫代碼（循環(huán)+判斷l(xiāng)owcostv是否為0）來實現(xiàn)尋找不為零的最小值的麻煩，提高了代碼執(zhí)行的效率。2.對lowcost和adjvex

9、進行更新，即：設(shè)剛加入最小生成樹的頂點為index，比較對于U-V中的每個頂點v:比較lowcost(v)和（v，index）邊的權(quán)值大小，如果（v，index）邊的權(quán)值小，則令lowcost(v)的值為該邊的權(quán)值，并將adjvex(v)的值等于indexfor j=1:len if lowcost(j)>graph_adjacent(j,index); lowcost(j)=graph_adjacent(j,index); adjvex(j)=index; end end3.將該邊保存tree(i,:)=adjvex(index),index;ii.結(jié)果如下求第一張圖的最小生成樹：求第

10、二張圖的最小生成樹：II . 用Krusal算法（避圈法）求最小生成樹i算法分析及需求分析，程序設(shè)計Kruskal算法的基本思想是：設(shè)無向連通網(wǎng)為G=（V，E），令G的最小生成樹為T=（U，TE），其初始狀態(tài)為U=V，TE=,這樣T中各頂點各自構(gòu)成一個連通分量。然后按照邊的權(quán)值由小到大的順序，依次考察邊集E中的各條邊。若被考察的邊的兩個頂點屬于T的兩個不同的連通分量，則將此邊加入到TE中去，同時把兩個連通分量連接成一個連通分量；若被考察邊的兩個結(jié)點屬于同一個連通分量，則舍去此邊，以免造成回路，如此下去，當T中的連通分量個數(shù)為1時，此連通分量便為G的一棵最小生成樹。顯然，Kruskal算法實現(xiàn)起

11、來要比prim算法復(fù)雜些。選擇合適的存儲結(jié)構(gòu)存儲圖，采用合適的排序算法對程序執(zhí)行效率的提高非常重要，采用簡單而明了的方法判斷邊的兩個端點是否在一個連通分支上更是尤為重要。一般來說，涉及Kruskal算法多采取邊集數(shù)組做為圖的存儲結(jié)構(gòu)，但考慮到matlab不像C語言那樣可以方便地動態(tài)的生成數(shù)組和釋放內(nèi)存，仍采取了鄰接矩陣的形式保存圖，用于測試的兩幅圖，分別保存為Graph11.M,Graph22.M.（注：鄰接矩陣的對角線元素設(shè)定為100）這樣既方便對邊進行操作，又方便對邊的頂點進行操作。使用鄰接矩陣容易引起的問題是：由于鄰接矩陣是對稱矩陣，比如graph_adjacent(1,2)和graph

12、_adjacent(2,1)代表的是同一條邊，所以當有一條邊被選入最小生成樹后，要對它的兩個結(jié)點分別進行更新。整個程序是以頂點為基本單位處理的。由于一條邊對應(yīng)兩個結(jié)點，取標號較小的頂點做為主要處理對象，并用它來尋址該邊所對應(yīng)的另一個結(jié)點。這樣規(guī)格化的好處在于：程序流程的每一步都會在自己的預(yù)測中，出現(xiàn)了錯誤易于查找。下面介紹一下一個matlab的built_in排序函數(shù)sort這個函數(shù)的功能非常強，也正因為采用了這個函數(shù)才使我的程序簡潔高效。Y，I=sort（A）；其中A為矩陣。則Y為將A中各列按從小到大排序后的結(jié)果，I為Y中的元素在原矩陣A中所在的行號。舉例如下對于判斷兩個點是否在同一個連通分

13、支，我的方法如下：聲明一數(shù)組tag保存每個結(jié)點所在的連通分支的標號，初始值為每個結(jié)點的標號，當兩個連通分量相連后則將它們的tag值設(shè)為一致程序流程圖：關(guān)鍵代碼說明：1 如何判斷兩個點是否在同一個連通分支將圖中每個頂點的tag值設(shè)為自身標號for j=1:len tag(j)=j;%關(guān)聯(lián)標志初始化，將每個頂點的關(guān)聯(lián)標志設(shè)為其本身end;當確定兩個頂點不在同一個連通分支時，將它們對應(yīng)的邊加入最優(yōu)邊集superedge中，并修改其中一個頂點的及其所在連通分支的各個點的tag值，使其和另一連通分支具有相同的tag值。if(tag(anotherpoint)=tag(index)%當兩個點不屬于一個連通

14、集時，這兩個點之間的邊為最小生成樹的邊 superedge(i,:)=index,anotherpoint;%將其加入最小生成樹的邊集中 i=i+1;%下標加1 %下面的語句的作用是將兩個連通分支變成一個連通分支，即tag值一樣 for j=1:len%以index的tag值為標準 if(tag(j)=tag(anotherpoint)&(j=anotherpoint)%遍搜tag數(shù)組，先將和anotherpoint tag值一樣的點的tag值變?yōu)閕ndex的tag值 tag(j)=tag(index); end end tag(anotherpoint)=tag(index);%將a

15、notherpoint的tag值變?yōu)閕ndex的tag值 end end注意：上面的紅色代碼部分，要先將連同分支的其他點的tag值變?yōu)閠ag（index），最后在改變tag（anotherpoint）的tag值，如果先將tag(anotherpoint)的值改變了，編號在anotherpoint之后的點的tag值就無法正確更新了2.尋找最小邊Y,I=sort(temp);%將temp的每列按從小到大排序，數(shù)組Y保存temp 排序后的結(jié)果，I中保存相應(yīng)結(jié)果對應(yīng)的在temp中的下標 cost_min=min(Y(1,:);%找出權(quán)值最小的邊 index=find(Y(1,:)=cost_min);

16、%找出權(quán)值最小的邊對應(yīng)的頂點 index=index(1);%一條邊對應(yīng)兩個節(jié)點，且不同的邊的權(quán)值可能一樣，這里為了方便處理人為規(guī)定了順序，取標號最小的頂點進行處理 anotherpoint=I(1,index);%找到該邊對應(yīng)的另一個頂點 %將該邊對應(yīng)的權(quán)值修改為最大，防止該邊在下次循環(huán)中再次被選為最優(yōu)邊 temp(index,anotherpoint)=100;temp(anotherpoint,index)=100;3.顯示模塊采用的代碼參見prim算法。ii.結(jié)果如下a 第一張圖的最小生成樹b 第二張圖的最小生成樹四擴展功能的完成（1）提供對算法效率（復(fù)雜度）進行評估的方法，并通過舉例

17、驗證，與分析得到的算法復(fù)雜度結(jié)果相對照；理論分析 設(shè)圖中的頂點數(shù)為n，則Prim算法要執(zhí)行n-1次外循環(huán)找齊最小邊，每次外循環(huán)又要執(zhí)行n次內(nèi)循環(huán)對lowcost和adjvex數(shù)組進行更新，所以Prim算法的時間復(fù)雜度為O(n2),與網(wǎng)中的邊數(shù)無關(guān)，因此適用于求稠密網(wǎng)的最小生成樹。 因為Kruskal算法是依次對圖中的邊進行操作，因此Kruskal算法的時間復(fù)雜度為O(elog2e),其中e為無向連通網(wǎng)中邊的個數(shù)。相對Prim算法而言，Kruskal算法適用于求稀疏網(wǎng)絡(luò)的最小生成樹。程序驗證1 隨機生成300×300的對稱稠密矩陣，用于觀測Kruskal和Prim算法的運行時間。（分別

18、在finallyprim和finallykruskal腳本文件中的主循環(huán)開始和結(jié)束為止加tic,toc）對稱矩陣采用如下方法生成。a=ceil*(rand(300);b=triu(a);c=b;a=a+c;for ii=1:300a(ii,ii)=0;%(for prim) or a(ii,ii)=1000%(for kruskal)end運行結(jié)果如下：a. primb. kruskal由此可見對于稠密圖prim算法優(yōu)于kruskal算法2 隨機生成一稀疏對稱矩陣，用于觀測kruskal和prim算法的運行時間稀疏對稱矩陣采用如下方法生成a=ones(300)*1000;%如果a(i,j)=1

19、000表明i,j兩點不連通a(:,2)=ceil(50*rand(1,300); a(2,:)=a(:,2);a(1,3)=1;a(3,1)=1;a(4,8)=2;a(8,4)=1;for ii=1:300 a(ii,ii)=0;%（for prim）end這是一個多播網(wǎng)，2號結(jié)點是廣播源，1，3結(jié)點和2相連外，還彼此相連，同理4，8結(jié)點。運行結(jié)果如下：a. Primb. kruskal3.結(jié)果對比(時間單位 seconds)稀疏圖稠密圖Prim0.1880.172Kruskal3.60922.719從表格的行的方向?qū)Ρ日f明：prim算法更適于處理稠密圖；kruskal算法更適于處理稀疏圖。從表格的列的方向?qū)Ρ日f明：似乎是prim算法在兩種場合都優(yōu)于kruskal算法，但這個結(jié)論是不正確的，因為我的kruskal算法還沒有達到最優(yōu)化。（2）從降低內(nèi)存消耗、減少計算時間的角度，對算法進行優(yōu)化。1.prim算法對于prim算法，我認為在我的思路范圍內(nèi)已經(jīng)達到了最優(yōu)。尤其得意的是尋找非零最小值的代碼實現(xiàn)，認為很具有matlab風格。k=lowcost>0;%k為一邏輯數(shù)組，它和lowcost同