# Prim's Minimum Spanning Treeby Isai Damier, Android Engineer @ Google

```/**************************************************************************
* 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:
*
*   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=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.
*
*
*  -- 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
*
*****************************************************************/
public List<Integer[]> minimumSpanningTree(Integer[][] G) {
final int n = G.length;
int[] prev = new int[n];
Arrays.fill(prev, -1);

while (!pq.isEmpty()) {
int v = pq.remove();
for (Integer u[] : pqNeighbors(G, pq, v)) {
//u is the vertex; u is the weight/link
prev[u] = 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++) {
}
}
return result;
}// minimumSpanningTree```
```package algorithms.graph;

import java.util.List;
import org.junit.After;
import org.junit.Test;
import static org.junit.Assert.*;
import org.junit.Before;

public class PrimMinimumSpanningTreeTest {

PrimMinimumSpanningTree mst;

@Before
public void setUp() throws Exception {
mst = new PrimMinimumSpanningTree();
}

@After
public void tearDown() throws Exception {
mst = null;
}

@Test
public void testMinimumSpanningTree() {
Integer[][] G = {{null, 6, 5, null, null, null, 8, 14},
{6, null, 12, null, null, null, null, null},
{5, 12, null, 9, null, 7, null, null},
{null, null, 9, null, null, null, null, null},
{null, null, null, null, null, 15, null, null},
{null, null, 7, null, 15, null, 10, null},
{8, null, null, null, null, 10, null, 3},
{14, null, null, null, null, null, 3, null}};
mst.minimumSpanningTree(G);

Integer[][] expected = {{1, 0, 6}, {2, 0, 5}, {3, 2, 9}, {4, 5, 15},
{5, 2, 7}, {6, 0, 8}, {7, 6, 3}};
List<Integer[]> result = mst.minimumSpanningTree(G);
for (int i = 0; i < expected.length; i++) {
for (int k = 0; k < expected[i].length; k++) {
if (expected[i][k] != result.get(i)[k]) {
fail(expected[i][k] + " vs " + result.get(i)[k]);
}
}
}

}
}
```