|
wolffd@0
|
1 function A = minimum_spanning_tree(C1, C2)
|
|
wolffd@0
|
2 %
|
|
wolffd@0
|
3 % Find the minimum spanning tree using Prim's algorithm.
|
|
wolffd@0
|
4 % C1(i,j) is the primary cost of connecting i to j.
|
|
wolffd@0
|
5 % C2(i,j) is the (optional) secondary cost of connecting i to j, used to break ties.
|
|
wolffd@0
|
6 % We assume that absent edges have 0 cost.
|
|
wolffd@0
|
7 % To find the maximum spanning tree, used -1*C.
|
|
wolffd@0
|
8 % See Aho, Hopcroft & Ullman 1983, "Data structures and algorithms", p 237.
|
|
wolffd@0
|
9
|
|
wolffd@0
|
10 % Prim's is O(V^2). Kruskal's algorithm is O(E log E) and hence is more efficient
|
|
wolffd@0
|
11 % for sparse graphs, but is implemented in terms of a priority queue.
|
|
wolffd@0
|
12
|
|
wolffd@0
|
13 % We partition the nodes into those in U and those not in U.
|
|
wolffd@0
|
14 % closest(i) is the vertex in U that is closest to i in V-U.
|
|
wolffd@0
|
15 % lowcost(i) is the cost of the edge (i, closest(i)), or infinity is i has been used.
|
|
wolffd@0
|
16 % In Aho, they say C(i,j) should be "some appropriate large value" if the edge is missing.
|
|
wolffd@0
|
17 % We set it to infinity.
|
|
wolffd@0
|
18 % However, since lowcost is initialized from C, we must distinguish absent edges from used nodes.
|
|
wolffd@0
|
19
|
|
wolffd@0
|
20 n = length(C1);
|
|
wolffd@0
|
21 if nargin==1, C2 = zeros(n); end
|
|
wolffd@0
|
22 A = zeros(n);
|
|
wolffd@0
|
23
|
|
wolffd@0
|
24 closest = ones(1,n);
|
|
wolffd@0
|
25 used = zeros(1,n); % contains the members of U
|
|
wolffd@0
|
26 used(1) = 1; % start with node 1
|
|
wolffd@0
|
27 C1(find(C1==0))=inf;
|
|
wolffd@0
|
28 C2(find(C2==0))=inf;
|
|
wolffd@0
|
29 lowcost1 = C1(1,:);
|
|
wolffd@0
|
30 lowcost2 = C2(1,:);
|
|
wolffd@0
|
31
|
|
wolffd@0
|
32 for i=2:n
|
|
wolffd@0
|
33 ks = find(lowcost1==min(lowcost1));
|
|
wolffd@0
|
34 k = ks(argmin(lowcost2(ks)));
|
|
wolffd@0
|
35 A(k, closest(k)) = 1;
|
|
wolffd@0
|
36 A(closest(k), k) = 1;
|
|
wolffd@0
|
37 lowcost1(k) = inf;
|
|
wolffd@0
|
38 lowcost2(k) = inf;
|
|
wolffd@0
|
39 used(k) = 1;
|
|
wolffd@0
|
40 NU = find(used==0);
|
|
wolffd@0
|
41 for ji=1:length(NU)
|
|
wolffd@0
|
42 for j=NU(ji)
|
|
wolffd@0
|
43 if C1(k,j) < lowcost1(j)
|
|
wolffd@0
|
44 lowcost1(j) = C1(k,j);
|
|
wolffd@0
|
45 lowcost2(j) = C2(k,j);
|
|
wolffd@0
|
46 closest(j) = k;
|
|
wolffd@0
|
47 end
|
|
wolffd@0
|
48 end
|
|
wolffd@0
|
49 end
|
|
wolffd@0
|
50 end
|
|
wolffd@0
|
51
|
