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

《計算機仿真》期末大作業(yè)Prim算法和Kruskal算法的Matlab實現(xiàn)05605劉禹050697（30）連線問題應用舉例：欲鋪設連結n個城市的高速公路，若i城與j城之間的高速公路造價為Cij，試設計一個線路圖，使總的造價最低。連線問題的數(shù)學模型就是圖論中在連通的賦權圖上求權最小的支撐樹。試用Matlab分別實現(xiàn)求最小支撐數(shù)的Prim算法和Krusal算法（避圈法）。.基本要求：1）畫出程序流程圖；2）對重點算法、變量和步驟進行解說說明；3）用以下兩圖對所寫算法的正確性進行考證。即輸入圖的信息，輸出對應圖的最小支撐樹及其權值。v26v79224334114186222v3163011419155v1v664352016v45v574484）剖析兩種算法的實現(xiàn)復雜度。.擴展要求：1）供給對算法效率（復雜度）進行評估的方法，并經(jīng)過舉例考證，與剖析獲得的算法復雜度結果相比較；2）從降低內(nèi)存耗費、減少計算時間的角度，對算法進行優(yōu)化。三．實驗步驟用Prim算法求最小生成樹．算法剖析及需求剖析，程序設計prim

算法的基本思想是：設

G=（V，E）是一個無向連通網(wǎng)，令

T=（U，TE）是

G的最小生成樹。T的初始狀態(tài)為

U={v0}（v0

）TE={}，而后重復履行下述操作：在全部

u

U，V-U的邊中找一條代價最小的邊（u，v）并入會合TE，同時v并入U，直至U=V為止。明顯，Prim算法的基本思想是以局部最優(yōu)化謀求全局的最優(yōu)化，并且，還波及到開端結點的問題。本程序達成的功能是：從圖中的隨意結點出發(fā)，都能夠找出最小生成樹實現(xiàn)方案剖析：Prim

算法的重點是怎樣找到連結

U和

V-U

的最短邊來擴大生成樹

T。設目前

T中有

k個點（即T的極點集U中有k個極點）則全部知足uU，vV-U的邊最多有k條，從這樣大的邊集中選用最短邊是不太經(jīng)濟的。利用MST性質(zhì)，能夠用下述方法結構候選最小邊集：對應V-U中的每個極點，保存從該極點到U中的各極點的最短邊，取候選邊最短邊集為V-U中的n-k個極點所關系的n-k條最短邊的會合。為表示候選最短邊集，需設置兩個一維數(shù)組lowcost[n]和adjvex[n],此中l(wèi)owcost用來保存會合V-U中的各極點與會合U中極點的最短邊的權值，lowcost[v]=0表示極點v已經(jīng)加入最小生成樹中；adjvex用來保存依賴于該邊在會合U中的極點。比以下式表示極點和極點之間的權值為wlowcost[i]=w;adjvex[i]=k;程序流程圖重點代碼說明：1．將用于考證算法正確性的兩幅圖用毗鄰矩陣的形式保存，分別保存為文件,（注：矩陣的對角線元素設置為零。）并在主程序finallyprim中直接進行調(diào)用。2．在輸入起點時應當給程序的閱讀者就該圖的極點數(shù)作出提示，不然的話使用者很可能會輸入越界下標。采納的方法以下len=length(graph_adjacent);%求圖中有多少個極點k=sprintf('pleaseinputthepointwhereyouwanttostart,dorememberitmustbebetween1and%d',len);start_point=input(k);%輸入最小生成樹產(chǎn)生起點采納了sprintf格式化字符串的方法，就防止了編程的人每次依據(jù)輸入圖的頂點數(shù)手動對提示作改正。成效以下：在對第一幅圖進行算法考證時在workspace會以下輸出:pleaseinputthepointwhereyouwanttostart,dorememberitmustbebetween1and7在對第二幅圖進行算法考證時在workspace會有以下輸出：pleaseinputthepointwhereyouwanttostart,dorememberitmustbebetween1and83．在輸出結果時為了使結果在workspace中輸出的清楚，令人了如指掌，也使用了sprintf格式化字符串的方法，代碼以下s=0;forii=1:len-1k=sprintf('最小生成樹第%d條邊：（%d,%d），權值為%d',ii,tree(ii,1),tree(ii,2),graph_adjacent(tree(ii,1),tree(ii,2)));disp(k);disp('');s=s+graph_adjacent(tree(ii,1),tree(ii,2));enddisp('最小生成樹的總代價為：')disp(s);4．下邊對算法的核心部分進行說明：在len-1次循環(huán)中，每次循環(huán)要達成以下三項工作找到最小邊，（需要求lowcost數(shù)組的最小非零值，因為0表示該邊已經(jīng)被加入到了最小生成樹中）因為是求非零的最小值，就不可以在直接用min函數(shù)了。我采納的方法是這樣的：k=lowcost>0;%k為一邏輯數(shù)組，它和lowcost同維，關于每一個位%置i假如lowcost(i)>0則k(i)=1%不然k(i)=0;稍候?qū)⒂眠@個數(shù)組進行協(xié)助尋址cost_min=min(lowcost(k));%找出lowcost中除0外的最小值index=find(lowcost==cost_min);%找出此最小值在lowcost中的下標，即找到相應的節(jié)點index=index(1);%因為最小值的下標可能不只一個，這里取第一個下標進行辦理lowcost(index)=0;%表示該節(jié)點已經(jīng)加入了最小生成樹中采納這類方法不單充分利用了matlab的built_in函數(shù)，還防止了自己編寫代碼（循環(huán)+判斷l(xiāng)owcost[v]能否為0）來實現(xiàn)找尋不為零的最小值的麻煩，提升了代碼履行的效率。2.對lowcost和adjvex進行更新，即：設剛加入最小生成樹的極點為index，比較關于U-V中的每個極點v:比較lowcost(v)和（v，index）邊的權值大小，假如（v，index）邊的權值小，則令lowcost(v)的值為該邊的權值，并將adjvex(v)的值等于indexforj=1:leniflowcost(j)>graph_adjacent(j,index);lowcost(j)=graph_adjacent(j,index);adjvex(j)=index;endend將該邊保存tree(i,:)=[adjvex(index),index];結果以下求第一張圖的最小生成樹：求第二張圖的最小生成樹：II.用Krusal算法（避圈法）求最小生成樹．算法剖析及需求剖析，程序設計Kruskal算法的基本思想是：設無向連通網(wǎng)為G=（V，E），令G的最小生成樹為T=（U，TE），其初始狀態(tài)為U=V，TE={},這樣T中各極點各自組成一個連通重量。而后依據(jù)邊的權值由小到大的次序，挨次觀察邊集E中的各條邊。若被觀察的邊的兩個極點屬于T的兩個不同的連通重量，則將此邊加入到TE中去，同時把兩個連通重量連結成一個連通重量；若被觀察邊的兩個結點屬于同一個連通重量，

則舍去此邊，免得造成回路，

這樣下去，當

T中的連通重量個數(shù)為

1時，此連通重量便為

G的一棵最小生成樹。明顯，Kruskal

算法實現(xiàn)起來要比

prim

算法復雜些。選擇適合的儲存結構儲存圖，采用適合的排序算法對程序履行效率的提升特別重要，采納簡單而了然的方法判斷邊的兩個端點能否在一個連通分支上更是尤其重要。一般來說，波及

Kruskal

算法多采納邊集數(shù)組做為圖的儲存結構，但考慮到

matlab

不像C語言那樣能夠方便地動向的生成數(shù)組和開釋內(nèi)存，仍采納了毗鄰矩陣的形式保存圖，用于測試的兩幅圖，分別保存為,.（注：毗鄰矩陣的對角線元素設定為100）這樣既方便對邊進行操作，又方便對邊的極點進行操作。使用毗鄰矩聲勢易惹起的問題是：因為毗鄰矩陣是對稱矩陣，比方graph_adjacent(1,2)和graph_adjacent(2,1)代表的是同一條邊，所以當有一條邊被選入最小生成樹后，要對它的兩個結點分別進行更新。整個程序是以極點為基本單位辦理的。因為一條邊對應兩個結點，取標號較小的極點做為主要處理對象，并用它來尋址該邊所對應的另一個結點。這樣規(guī)格化的利處在于：程序流程的每一步都會在自己的展望中，出現(xiàn)了錯誤易于查找。下邊介紹一下一個matlab的built_in排序函數(shù)sort這個函數(shù)的功能特別強，也正因為采納了這個函數(shù)才使我的程序簡短高效。[Y，I]=sort（A）；此中A為矩陣。則Y為將A中各列按從小到大排序后的結果，I為Y中的元素在原矩陣A中所在的行號。舉比以下關于判斷兩個點能否在同一個連通分支，我的方法以下：申明一數(shù)組tag保存每個結點所在的連通分支的標號，初始值為每個結點的標號，當兩個連通重量相連后則將它們的tag值設為一致程序流程圖：重點代碼說明：1．怎樣判斷兩個點能否在同一個連通分支①將圖中每個極點的tag值設為自己標號forj=1:lentag(j)=j;%關系標記初始化，將每個極點的關系標記設為其自己end;②當確立兩個極點不在同一個連通分支時，將它們對應的邊加入最優(yōu)邊集superedge中，并改正此中一個極點的及其所在連通分支的各個點的tag值，使其和另一連通分支擁有同樣的tag值。if(tag(anotherpoint)~=tag(index))%當兩個點不屬于一個連通集時，這兩個點之間的邊為最小生成樹的邊superedge(i,:)=[index,anotherpoint];%將其加入最小生成樹的邊集中i=i+1;%下標加1%下邊的語句的作用是將兩個連通分支變?yōu)橐粋€連通分支，即tag值同樣forj=1:len%以index的tag值為標準if((tag(j)==tag(anotherpoint))&(j~=anotherpoint))%遍搜tag數(shù)組，先將和anotherpointtag值同樣的點的tag值變?yōu)閕ndex的tag值tag(j)=tag(index);endendtag(anotherpoint)=tag(index);%將anotherpoint的tag值變?yōu)閕ndex的tag值endend注意：上邊的紅色代碼部分，要先將連同分支的其余點的tag值變?yōu)閠ag（index），最后在改變tag（anotherpoint）的tag值，假如先將tag(anotherpoint)的值改變了，編號在anotherpoint以后的點的tag值就沒法正確更新了找尋最小邊[Y,I]=sort(temp);%將temp的每列按從小到大排序，數(shù)組Y保存temp排序后的結果，I中保存相應結果對應的在temp中的下標cost_min=min(Y(1,:));%找出權值最小的邊index=find(Y(1,:)==cost_min);%找出權值最小的邊對應的極點index=index(1);%一條邊對應兩個節(jié)點，且不一樣的邊的權值可能同樣，這里為了方便辦理人為規(guī)定了次序，取標號最小的極點進行辦理anotherpoint=I(1,index);%找到該邊對應的另一個極點將該邊對應的權值改正為最大，防備該邊在下次循環(huán)中再次被選為最優(yōu)邊temp(index,anotherpoint)=100;temp(anotherpoint,index)=100;顯示模塊采納的代碼拜見prim算法。結果以下a．第一張圖的最小生成樹b．第二張圖的最小生成樹四．擴展功能的達成（1）供給對算法效率（復雜度）進行評估的方法，并經(jīng)過舉例考證，與剖析獲得的算法復雜度結果相比較；⑴理論剖析設圖中的極點數(shù)為n，則Prim算法要履行n-1次外循環(huán)找齊最小邊，每次外循環(huán)又要執(zhí)行n次內(nèi)循環(huán)對lowcost和adjvex數(shù)組進行更新，所以Prim算法的時間復雜度為O(),與網(wǎng)中的邊數(shù)沒關，所以合用于求濃密網(wǎng)的最小生成樹。因為Kruskal算法是挨次對圖中的邊進行操作，所以Kruskal算法的時間復雜度為O(e),此中e為無向連通網(wǎng)中邊的個數(shù)。相對Prim算法而言，Kruskal算法合用于求稀疏網(wǎng)絡的最小生成樹。⑵程序考證1．隨機生成300300的對稱濃密矩陣，用于觀察Kruskal和Prim算法的運轉時間。（分別在finallyprim和finallykruskal腳本文件中的主循環(huán)開始和結束為止加tic,toc）對稱矩陣采納以下方法生成。a=ceil*(rand(300));b=triu(a);c=b’;a=a+c;forii=1:300a(ii,ii)=0;%(forprim)ora(ii,ii)=1000%(forkruskal)end運轉結果以下：primkruskal因而可知關于濃密圖prim算法優(yōu)于kruskal算法2．隨機生成一稀少對稱矩陣，用于觀察kruskal和prim算法的運轉時間稀少對稱矩陣采納以下方法生成a=ones(300)*1000;%假如a(i,j)=1000表示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;forii=1:300a(ii,ii)=0;%（forprim）end這是一個多播網(wǎng)，2號結點是廣播源，1，3結點和2相連外，還相互相連，同理4，結點。運轉結果以下：Primkruskal3.結果對照(時間單位seconds)稀少圖濃密圖PrimKruskal從表格的行的方向?qū)φ照f明：prim算法更適于辦理濃密圖；kruskal算法更適于辦理稀少圖。從表格的列的方向?qū)φ照f明：仿佛是prim算法在兩種場合都優(yōu)于kruskal算法，但這個結論是不正確的，因為我的kruskal算法還沒有達到最優(yōu)化。2）從降低內(nèi)存耗費、減少計算時間的角度，對算法進行優(yōu)化。算法關于prim算法，我以為在我的思路范圍內(nèi)已經(jīng)達到了最優(yōu)。特別喜悅的是找尋非零最小值的代碼實現(xiàn)，以為很擁有matlab風格。k=lowcost>0;%k