PRIM Prim's algorithm for calculating a minimal spanning tree. [E] = PRIM(AADJ) Implementation of Prim's algorithm for calculating a minimal spanning tree from a graph adjacency matrix. This implementation can incorporate negative edge weights. Create a maximal spanning tree by specifying the negative of the graph adjacency matrix. Inputs: AADJ : A graph adjacency matrix, including the possibility of negative edge weights. Outputs: E : Matrix with two columns describing the resulting minimal weight spanning tree. Each row gives the maximal cliques for a branch of the tree.
0001 function [E] = prim(Aadj) 0002 %PRIM Prim's algorithm for calculating a minimal spanning tree. 0003 % [E] = PRIM(AADJ) 0004 % 0005 % Implementation of Prim's algorithm for calculating a minimal spanning 0006 % tree from a graph adjacency matrix. This implementation can incorporate 0007 % negative edge weights. Create a maximal spanning tree by specifying 0008 % the negative of the graph adjacency matrix. 0009 % 0010 % Inputs: 0011 % AADJ : A graph adjacency matrix, including the possibility of 0012 % negative edge weights. 0013 % 0014 % Outputs: 0015 % E : Matrix with two columns describing the resulting minimal weight 0016 % spanning tree. Each row gives the maximal cliques for a branch 0017 % of the tree. 0018 0019 % MATPOWER 0020 % Copyright (c) 2013-2016, Power Systems Engineering Research Center (PSERC) 0021 % by Daniel Molzahn, PSERC U of Wisc, Madison 0022 % 0023 % This file is part of MATPOWER. 0024 % Covered by the 3-clause BSD License (see LICENSE file for details). 0025 % See http://www.pserc.cornell.edu/matpower/ for more info. 0026 0027 0028 Vnew = 1; 0029 E = []; 0030 nnode = size(Aadj,1); 0031 cols(1).c = sparse(Aadj(Vnew(1),:)~=0); 0032 cols(1).c(Vnew) = 0; 0033 while length(Vnew) < nnode 0034 % Choose an edge (u,v) with minimal weight so that u is in Vnew and 0035 % v is not 0036 0037 % Find the best available edge 0038 bestedge.value = inf; 0039 bestedge.row = []; 0040 bestedge.col = []; 0041 for i=1:length(Vnew) 0042 0043 [tempMaxVal,tempMaxCol] = min(Aadj(Vnew(i),cols(i).c)); 0044 if tempMaxVal < bestedge.value 0045 bestedge.value = tempMaxVal; 0046 bestedge.row = Vnew(i); 0047 0048 tempc = find(cols(i).c,tempMaxCol); 0049 bestedge.col = tempc(tempMaxCol); 0050 end 0051 end 0052 0053 Vnew = [Vnew; bestedge.col]; 0054 cols(length(Vnew)).c = sparse(Aadj(Vnew(end),:) ~= 0); 0055 cols(length(Vnew)).c(Vnew) = 0; 0056 0057 for i=1:length(Vnew)-1 0058 cols(i).c(Vnew(end)) = 0; 0059 end 0060 0061 E = [E; bestedge.row bestedge.col]; 0062 0063 if isempty(bestedge.row) || isempty(bestedge.col) 0064 error('prim: Error in Prim''s Algorithm. System is probably separated into multiple island. Ensure connected system and try again.'); 0065 end 0066 0067 end 0068 V = Vnew;