最小生成樹matlab實(shí)現(xiàn)

1、rimclearall;closeall;Graph1;%調(diào)用Graph1M文件，產(chǎn)生圖1的鄰接矩陣%Graph2;%調(diào)用Graph2M文件，產(chǎn)生圖2的鄰接矩陣len=length(graph_adjacent);%求圖中有多少個(gè)頂點(diǎn)k=sprintf(pleaseinputthepointwhereyouwanttostart,dorememberitmustbebetween1and%d,len);start_point=input(k);%輸入最小生成樹產(chǎn)生起點(diǎn)while(start_point0;%k為一邏輯數(shù)組，它和lowcost同維，對(duì)于每一個(gè)位置i1lowcost(i)0則k(i

2、)=1%否則k(i)=0;稍候?qū)⒂眠@個(gè)數(shù)組進(jìn)行輔助尋址cost_min=min(lowcost(k);%找出lowcost中除0外的最小值index=find(lowcost=cost_min);%找出此最小值在lowcost中的下標(biāo)，即找到相應(yīng)的節(jié)點(diǎn)index=index(1);%因?yàn)樽钚≈档南聵?biāo)可能不止一個(gè)，這里取第一個(gè)下標(biāo)進(jìn)行處理lowcost(index)=0;%表明該節(jié)點(diǎn)已經(jīng)加入了最小生成樹中tree(i,:)=adjvex(index),index;%對(duì)lowcost和adjvex進(jìn)行更新forj=1:leniflowcost(j)graph_adjacent(j,index);l

3、owcost(j)=graph_adjacent(j,index);adjvex(j)=index;endendend;%*結(jié)果顯示模塊*s=0;forii=1:len-1k=sprintf(最小生成樹第d條邊：(d,%d),權(quán)值為%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);%求最小生成樹的代價(jià)end%顯示最小生成樹的代價(jià)disp(最小生成樹的總代價(jià)為：)disp(s

4、);kruskalclearall;closeall;Graph11;%調(diào)用以鄰接矩陣儲(chǔ)存的圖所在的M文件%Graph22;len=length(graph_adjacent);%計(jì)算圖中的頂點(diǎn)數(shù)temp=graph_adjacent;%將原圖內(nèi)容拷貝到temp中，以防對(duì)原圖做改動(dòng)superedge=zeros(len-1,2);%用于保存生成最小生成樹的邊i=1;%扌旨向superedge的下標(biāo)forj=1:lentag(j)=j;%關(guān)聯(lián)標(biāo)志初始化，將每個(gè)頂點(diǎn)的關(guān)聯(lián)標(biāo)志設(shè)為其本身end;%以下的循環(huán)完成kruskal算法while(superedge(len-1,1)=0)Y,I=sort(

5、temp);%將temp的每列按從小到大排序，數(shù)組Y保存temp排序后的結(jié)果，I中保存相應(yīng)結(jié)果對(duì)應(yīng)的在temp中的下標(biāo)cost_min=min(Y(1,:);%找出權(quán)值最小的邊index=find(Y(1,:)=cost_min);%找出權(quán)值最小的邊對(duì)應(yīng)的頂點(diǎn)index=index(1);%一條邊對(duì)應(yīng)兩個(gè)節(jié)點(diǎn)，且不同的邊的權(quán)值可能一樣，這里為了方便處理人為規(guī)定了順序，取標(biāo)號(hào)最小的頂點(diǎn)進(jìn)行處理anotherpoint=I(1,index);%找到該邊對(duì)應(yīng)的另一個(gè)頂點(diǎn)%將該邊對(duì)應(yīng)的權(quán)值修改為最大，防止該邊在下次循環(huán)中再次被選為最優(yōu)邊temp(index,anotherpoint)=100;temp

6、(anotherpoint,index)=100;if(tag(anotherpoint)=tag(index)%當(dāng)兩個(gè)點(diǎn)不屬于一個(gè)連通集時(shí)，這兩個(gè)點(diǎn)之間的邊為最小生成樹的邊superedge(i,:)=index,anotherpoint;%將其加入最小生成樹的邊集中i=i+1;%下標(biāo)加1%下面的語句的作用是將兩個(gè)連通分支變成一個(gè)連通分支，即tag值一樣forj=1:len%以index的tag值為標(biāo)準(zhǔn)if(tag(j)=tag(anotherpoint)&(j=anotherpoint)%遍搜tag數(shù)組，先將和anotherpointtag值一樣的點(diǎn)的tag值變?yōu)閕ndex的tag值tag(j)=tag(index);endendtag(anotherpoint)=tag(index);%將anotherpoint的tag值變?yōu)閕ndex的tag值endend%*結(jié)果顯示模塊*s=0;forii=1:len-1k=sprintf(最小生成樹第d條邊：(d,%d),權(quán)值為%d,ii,superedge(ii,superedge(ii,2),graph_adjacent(superedge(ii,1),superedge(ii,);%格式化字符串%disp(k);顯示%disp