kruskal.m

10组图论编程

function y=kruskal(N)
%N为图的权矩阵，N应为对称矩阵，kruskal求图的最小生成树。
if nargin==0
    N=[0 9 2 4 7;9 0 3 4 0;2 3 0 8 5;4 4 8 0 6;7 0 5 6 0];
end;
a=tril(N);
%a是N的上三角矩阵。
[i,j]=find(a~=0);
b=a(find(a~=0));
data=[i';j';b'];
index=data(1:2,:);
loop=length(a)-1;
result=[];
%最小生成树的边的个数
while length(result)<loop
   temp=min(data(3,:));
   flag=find(data(3,:)==temp);
   flag=flag(1);
   v1=index(1,flag);v2=index(2,flag);
   if index(1,flag)~=index(2,flag)
       result=[result,data(:,flag)];
   end
   if v1>v2
       index(find(index==v1))=v2;
   else
       index(find(index==v2))=v1;
   end
   data(:,flag)=[];
   index(:,flag)=[];
end
disp(result);
y=result;
end;