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 % $Id: prim.m 2272 2014-01-17 14:15:47Z ray $ 0021 % by Daniel Molzahn, PSERC U of Wisc, Madison 0022 % Copyright (c) 2013-2014 by Power System Engineering Research Center (PSERC) 0023 % 0024 % This file is part of MATPOWER. 0025 % See http://www.pserc.cornell.edu/matpower/ for more info. 0026 % 0027 % MATPOWER is free software: you can redistribute it and/or modify 0028 % it under the terms of the GNU General Public License as published 0029 % by the Free Software Foundation, either version 3 of the License, 0030 % or (at your option) any later version. 0031 % 0032 % MATPOWER is distributed in the hope that it will be useful, 0033 % but WITHOUT ANY WARRANTY; without even the implied warranty of 0034 % MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 0035 % GNU General Public License for more details. 0036 % 0037 % You should have received a copy of the GNU General Public License 0038 % along with MATPOWER. If not, see <http://www.gnu.org/licenses/>. 0039 % 0040 % Additional permission under GNU GPL version 3 section 7 0041 % 0042 % If you modify MATPOWER, or any covered work, to interface with 0043 % other modules (such as MATLAB code and MEX-files) available in a 0044 % MATLAB(R) or comparable environment containing parts covered 0045 % under other licensing terms, the licensors of MATPOWER grant 0046 % you additional permission to convey the resulting work. 0047 0048 0049 Vnew = 1; 0050 E = []; 0051 nnode = size(Aadj,1); 0052 cols(1).c = sparse(Aadj(Vnew(1),:)~=0); 0053 cols(1).c(Vnew) = 0; 0054 while length(Vnew) < nnode 0055 % Choose an edge (u,v) with minimal weight so that u is in Vnew and 0056 % v is not 0057 0058 % Find the best available edge 0059 bestedge.value = inf; 0060 bestedge.row = []; 0061 bestedge.col = []; 0062 for i=1:length(Vnew) 0063 0064 [tempMaxVal,tempMaxCol] = min(Aadj(Vnew(i),cols(i).c)); 0065 if tempMaxVal < bestedge.value 0066 bestedge.value = tempMaxVal; 0067 bestedge.row = Vnew(i); 0068 0069 tempc = find(cols(i).c,tempMaxCol); 0070 bestedge.col = tempc(tempMaxCol); 0071 end 0072 end 0073 0074 Vnew = [Vnew; bestedge.col]; 0075 cols(length(Vnew)).c = sparse(Aadj(Vnew(end),:) ~= 0); 0076 cols(length(Vnew)).c(Vnew) = 0; 0077 0078 for i=1:length(Vnew)-1 0079 cols(i).c(Vnew(end)) = 0; 0080 end 0081 0082 E = [E; bestedge.row bestedge.col]; 0083 0084 if isempty(bestedge.row) || isempty(bestedge.col) 0085 error('prim: Error in Prim''s Algorithm. System is probably separated into multiple island. Ensure connected system and try again.'); 0086 end 0087 0088 end 0089 V = Vnew;