function [out,len]=kruskal(map)
%求最小生成樹(shù)算法,通過(guò)kruskal算法求最優(yōu)樹(shù),并給出相應(yīng)圖像. 
%用法:
%	首先輸入矩陣: 
%		map=[起點(diǎn)1 終點(diǎn)1 邊長(zhǎng)1;起點(diǎn)2 終點(diǎn)2  邊長(zhǎng)2;............;起點(diǎn)n 終點(diǎn)n 邊長(zhǎng)n]
%	再用[out,len]=kruskal(map)求最優(yōu)樹(shù)
%參數(shù)說(shuō)明
%	map----3列鄰接矩陣,每行表示一條邊.第一列表示起點(diǎn),第二列表示終點(diǎn),第三列表示邊長(zhǎng)
%	out---輸出邊陣:[起點(diǎn) 終點(diǎn)]
%	len---輸出最優(yōu)樹(shù)的總長(zhǎng)度
%
%例如  
%		clear;map=[1 2 30;2 4 5;2 5 50;3 2 6;4 3 1;1 4 20;1 5 30]
%		[out,len]=kruskal(map)
%
%本算法調(diào)用由VC++6.0程序crusal1.c生成的MEX文件kruskal1.dll求得最小生成樹(shù),
%	表示無(wú)窮大的數(shù)值上界(默認(rèn)10000)
%
%See also DIJKSTRA,LPINT,DP,BNBGUI,BNB18,

%By S. J. Lu 2000

mx=0;
[m,n]=size(map);
mx=max(max(map(:,1:2)));
op=10000*ones(mx,mx);
for i=1:m
   op(map(i,1),map(i,2))=map(i,3);
   op(map(i,2),map(i,1))=map(i,3);
end
[out,len]=krusk(op);
out=out';

% 畫(huà)圖
close;
 set(gcf,'numbertitle','off');
 set(gcf,'name','Kruskal');
 set(gca,'visible','off');
 axis square;
 hold on;
 
 b=linspace(0,2*pi,mx+1);
 b1=10*sin(b);
 b2=10*cos(b);
 plot(b1,b2,'ko');
 
 hh=char(49:48+mx);
 for i=1:mx
    text(b1(i)+1,b2(i),hh(i));
 end;
 map
 for j=1:m
   for i=1:2
     c1(i)=b1(map(j,i));
     c2(i)=b2(map(j,i));
    end;
    plot(c1,c2,':');
end;

 k1=length(out);
 for i=1:k1
   for j=1:2
      d1(j)=b1(out(i,j));
      d2(j)=b2(out(i,j));
   end
   h=plot(d1,d2,'r');
   set(h,'linewidth',2);
 end 
 legend(h,'粗線為最優(yōu)樹(shù)');
 hold off