www.pudn.com > ConstrainedEM.zip > kruskal.m

function [treeCost,treeArcs] = Kruskal(E,costs) 
 
% Kruskal's algorithm to find a minimal spanning tree 
% E is node-arc incidence matrix of graph, costs is vector of arc costs. 
 
% For use in course Mathematics 2A1. 
% 
% Copyright (c) March 1997, Alistair Mees, University of Western Australia.  
% 
% This program may be freely used for education but may not be 
% sold or used for commercial purposes without my express written 
% permission. 
% 
% email: Alistair.Mees@uwa.edu.au 
 
 
[nNodes,nArcs] = size(E); 
 
[q,sortedArcIndices] = sort(costs); 
treeArcs = [sortedArcIndices(1)]; 
 
for a = sortedArcIndices(2:nArcs) 
 
  if length(treeArcs) >= nNodes-1 
    break; 
  end 
   
  % Try to find a path in the tree from one end of a to the other. 
  % If there is none, we can add arc a to the tree we are building: 
  n1 = find(E(:,a)==1); 
  n2 = find(E(:,a)==-1); 
  path = paintedPath(E(:,treeArcs),[],n1,n2,1);  % Painted path algorithm, all arcs green, no display 
   
  if isempty(path) 
    treeArcs = [treeArcs,a]; 
  end 
   
end 
 
treeCost = sum(costs(treeArcs));