最小生成樹matlab實現

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

2、)=1%否則k(i)=0;稍候將用這個數組進行輔助尋址cost_min=min(lowcost(k);%找出lowcost中除0外的最小值index=find(lowcost=cost_min);%找出此最小值在lowcost中的下標，即找到相應的節(jié)點index=index(1);%因為最小值的下標可能不止一個，這里取第一個下標進行處理lowcost(index)=0;%表明該節(jié)點已經加入了最小生成樹中tree(i,:)=adjvex(index),index;%對lowcost和adjvex進行更新forj=1:leniflowcost(j)graph_adjacent(j,index);l

3、owcost(j)=graph_adjacent(j,index);adjvex(j)=index;endendend;%*結果顯示模塊*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);%求最小生成樹的代價end%顯示最小生成樹的代價disp(最小生成樹的總代價為：)disp(s

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

5、temp);%將temp的每列按從小到大排序，數組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

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