II用Krusal算法避圈法求最小生成樹

1、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é)點屬于同一個連通分量，則舍去此邊，以免造成回路，如此下去，當(dāng)T中的連通分量個數(shù)為1時，此連通分量便為G的一棵最小生成樹。顯然，Kruskal算法實現(xiàn)起來要比prim算法復(fù)

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

3、2,1)代表的是同一條邊，所以當(dāng)有一條邊被選入最小生成樹后，要對它的兩個結(jié)點分別進(jìn)行更新。整個程序是以頂點為基本單位處理的。由于一條邊對應(yīng)兩個結(jié)點，取標(biāo)號較小的頂點做為主要處理對象，并用它來尋址該邊所對應(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中所在的行號。舉例如下對于判斷兩個點是否在同一個連通分支，我的方法如下：聲

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

5、邊為最小生成樹的邊 superedge(i,:)=index,anotherpoint;%將其加入最小生成樹的邊集中 i=i+1;%下標(biāo)加1 %下面的語句的作用是將兩個連通分支變成一個連通分支，即tag值一樣 for j=1:len%以index的tag值為標(biāo)準(zhǔn) 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);%將anotherpoin

6、t的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中的下標(biāo) cost_min=min(Y(1,:);%找出權(quán)值最小的邊 index=find(Y(1,:)=cost_min);%找出權(quán)值最小的邊對應(yīng)的頂點 index=index(1);%一條邊對應(yīng)兩個節(jié)點，且不同的邊的權(quán)值可能一樣，這里為了方便處理人為規(guī)定了順序，取標(biāo)號最小的頂點進(jìn)行處理 anotherpoint=I(1,index);%找到該邊對應(yīng)的另一個頂點 %將該邊對應(yīng)的權(quán)值修改