mst_k.m

清华大学运筹学课件

%MST_k.m
%This program solves the Minimum Spanning Tree problem by using Kruskal Algorithm.')
n=input('Enter the vertices number of the graph:n= ')
W=input('Enter the weight adjacent matrix of the graph:[W(1,1),..,W(1,n);..;W(n,1),..,W(n,n)]=') 
%W(i,i)=inf instead of "=0"

%preparation

T=zeros(n); %the weight adjacent matrix of the Minimum Spanning Tree 
WW=W;
   for i=1:n 
      for j=1:n
         if W(i,j)==inf  WW(i,j)=0; 
         end
      end
   end
m=((nnz(WW))/2);  %the number of edges in the graph
j=0; %number of edges in the Minimum Spanning Tree

%main steps

for i=1:m %the number of chosen edges
   
   if j<(n-1) %the stop-condition of the algorithm is |E|=|V|-1.
      
%step0: pick out the minimum edge W(a,b)
      
      min=inf; a=0; b=0;     
      for k=1:n
         for l=(k+1):n
            if W(k,l)<=min  min=W(k,l); a=k; b=l; end 
         end
      end
%step0 end
      
%step1

%T=T+e(a,b)
      T(a,b)=W(a,b); T(b,a)=W(a,b); 
%check the cycle 
      f=0; %have no cycle
      P=zeros(2,m);  y=0; 
      for i=1:n
         for v=(i+1):n
            if T(i,v)~=0    y=y+1; P(1,y)=i; P(2,y)=v;  
            end
         end
      end
      for y=1:m
         if P(1,y)<P(2,y)
            for l=(y+1):m
               if P(1,l)==P(2,y)  P(1,l)=P(1,y);
               elseif P(2,l)==P(2,y)  P(2,l)=P(1,y);
               end
            end
            P(2,y)=P(1,y); 
         elseif P(2,y)<P(1,y)
            for l=(y+1):m
               if P(1,l)==P(1,y)  P(1,l)=P(2,y);
               elseif P(2,l)==P(1,y)  P(2,l)=P(2,y);
               end
            end
            P(1,y)=P(2,y);
         elseif (P(1,y)+P(2,y))~=0   f=1; %have a cycle
            break 
         end
      end
      
      if f==1   T(a,b)=0; T(b,a)=0; %goto step2
      else j=j+1; %goto step3
      end
      W(a,b)=inf;
   else %|E|=|V|-1
      MST=T;
      input('The weight adjacent matrix of the Minimum Spanning Tree of the graph is:') 
      MST
      break
     
   end  
       
     
end

if j<(n-1) %|E|<|V|-1
   input('The graph doesn"t include a Minimum Spanning Tree.')  
end