Prim's Minimum Spanning Tree
by Isai Damier, Android Engineer @ Google

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/**************************************************************************
 * Author: Isai Damier
 * Title: Prim's Minimum Spanning Tree
 * Project: geekviewpoint
 * Package: algorithm.graph
 *
 * Statement:
 *   Given a connected undirected graph, find a tree that comprises all the
 *   vertices such that the total weight of all the edges in the tree
 *   is minimal.
 *
 *   The difference between a graph and a tree is this:
 *   for a tree there is only one sequence of edges between
 *   any two vertices; no such guaranty is made for a graph.
 *
 *   The minimum spanning tree (MST) algorithm assumes the worst
 *   about the input graph: that there are more than one path
 *   (i.e. sequence of edges) between any two vertices.
 *   Jarnik-Prim's algorithm then proceeds as follows:
 *
 *   1] Start with an empty tree T
 *   2] Remove an arbitrary vertex from the graph G and add it
 *      to the tree T.
 *   3] a) For each remaining vertex on the graph G
 *      b) find the vertex v on the graph that is the closest
 *         distance from any vertex already on the tree.
 *      c) Remove v from the graph and add it to the tree.
 **************************************************************************/
  
package algorithms.graph;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
 
public class PrimMinimumSpanningTree {
 
  /******************************************************************
   * Function: minimumSpanningTree
   *
   * @param G: adjacency matrix representing the weighted graph. This
   *           is perforce a square matrix. The keys are vertices
   *           and each value is the weight of the edge linking
   *           those vertices. For example, G[1][5]=23 means
   *           an edge of weight 23 connects vertex 1 and vertex 5.
   *
   * @return Set<String>
   *
   * Implementation Details: Two details are important for
   *   understanding this implementation.
   *   1) Arrays pred[] and link[] are used to prepare each vertex
   *      before it is added to the MST.
   *   2) A vertex is considered in the MST once it is removed from
   *      the priority queue pq.
   *
   *  1] Start with an empty tree T
   *
   *  -- The minimum spanning tree (MST) is considered empty if
   *     all of the following three things are true:
   *     1) for all v, prev[v]=-1. Normally prev[] tracks the
   *        parent vertex x to which a child vertex v is linked
   *         to the tree, as prev[v]=x. Since -1 is not a valid
   *         vertex, prev[v] = -1 means v is the root.
   *     2) for all v, link[v] = infinity. link[] tracks the edge
   *        w that links a child vertex v to the tree by some
   *        parent vertex x. if v is an infinite distance away
   *        from x, then v is effectively not on the tree.
   *     3) all the vertices are in the priority queue pq.
   *
   *  2] Remove an arbitrary vertex from the graph G and add it
   *      to the tree T.
   *
   *  --  The first vertex x on the tree will be the root. So
   *      set link[x]=0. We will actually remove x from the
   *      graph when we dequeue pq.
   *
   *   3a] For each remaining vertex v on the graph G
   *
   *   -- this is simply a while loop checking that pq is not empty
   *
   *   3b-c] find the vertex v on the graph that is the closest distance
   *         from any vertex already on the tree. Remove v from the
   *         graph and add it to the tree.
   *
   *   -- When we remove v from pq, we at once remove it from the graph
   *      so to speak and add it to the tree T.
   *
   *      After removing v from the graph, we relax its neighbors and
   *      prepare them for admission into T. To relax a vertex, we
   *      apply the triangle inequality: if link[u] > G[v][u] then
   *      set link[u]=G[v][u].
   *
   *****************************************************************/
  public List<Integer[]> minimumSpanningTree(Integer[][] G) {
    final int n = G.length;
    int[] prev = new int[n];
    Arrays.fill(prev, -1);
    int[] link = new int[n];
    Arrays.fill(link, Integer.MAX_VALUE);
    link[0] = 0;
 
    PriorityQueue<Integer[]> pq = createPriorityQueue(link);
 
    while (!pq.isEmpty()) {
      pq.add(pq.remove());// reorder the queue
      int v = pq.remove()[0];
      for (Integer u[] : pqNeighbors(G, pq, v)) {
        //u[0] is the vertex; u[1] is the weight/link
        if (link[u[0]] > G[v][u[0]]) {
          link[u[0]] = G[v][u[0]];
          u[1] = link[u[0]];//update in pq
          prev[u[0]] = v;
        }
      }
    }//while
 
    /* How you implement the following is up to you.
     * You can print it or whatever. I am creating
     * a list of array elements {v,x,edge} where edge
     * is the edge connecting vertex x to vertex v.
     */
    List<Integer[]> result = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      if (0 != link[i]) {
        result.add(new Integer[]{i, prev[i], link[i]});
      }
    }
    return result;
  }// minimumSpanningTree