Minimum Spanning Tree (MST)

Minimum Spanning Trees: Kruskal and Prim's Algorithms

The video, below, gives a good theoretical description of Kruskal and Prims algorithms. After watching that video you should also review the concept of disjoint sets which is shown in the second video and also described here. You will need to understand this concept to code a real-world implementation of these MST algorithms. 

Practice With Kruskal and Prim's Algorithms

Use either Kruskal or Prim's algorithm to solve the Min-Cost-to-Connect-All-Points problem in LeetCode. 

Note that the term Manhattan Distance referenced in this LeetCode problem refers to the same concept as Taxicab Distance shown in the video below:

Prims Project

We would like to generate a Minimum Spanning Tree (MST) using Prim's Algorithm starting at Node A for this Graph:

The final MST should be the one shown below to the left. Its adjacency matrix is shown to the right.

Prim's Algorithm Pseudocode

Here is the algorithm you should implement. You should use an Adjacency Matrix to represent the underlying graphs.

1. Modify your Adjacency Matrix project to hold weights for each edge.

2. Create a set visited (initially empty) that keeps track of vertices already included in MST. 

3. Add the starting node to the visited set.

4. While visited doesn’t include all vertices 

   • Check all the nodes that have not yet been visited but have an edge that connects to the MST. 

   • Find such a node with the smallest value edge.

   • Add the new edge to the MST

   • Mark the new node visited

5. Print the answer

Staring Code for Prim's Assignment

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Prims {

private static class Edge {
        int from;
        int to;

        public Edge(int from, int to) {
            this.from = from;
            this.to = to;
        }

        @Override public String toString() {
            return "(" + from + "," + to + ")";
        }
    }

    int [] [] matrix;
    int [] [] mstMatrix;

   // you can use a different data structure for visited if you like
    Set<Integer> visited;  

    public Prims(int[][] matrix) {
        this.matrix = matrix;  // original graph matrix
        this.mstMatrix = new int[matrix.length][matrix.length];  // solution matrix
        this.visited = new HashSet<>();
    }

// method nextEdgeToVisit is the heart of the algorithm.
// it calculates the next edge to be added to the MST. it returns null if all nodes/edges have been added/visited.
private Edge nextEdgeToVisit() {
      // start by creating an answer variable of type Edge that is initially set to null.

    // check the size of the visited set and compare it to the length of the answer matrix  (number of nodes in the graph)
    // if these two match, there is no need to run this method since the MST should be finished. so just return null;

   // if we get here, there must be at least one unvisited node in the graph remaining.

   // create a variable called minEdgeValue and set it to a large number (Integer.MAX_VALUE)

   // iterate over the visited set (each node already in the MST)
  // for each node in the visited set, check each node that is connected to (has an edge with) the visited node
  // if the node being checked has not been visited and has an edge with the visited node and has an edge value
  // that is less than what is currently stored in minEdgeValue, update the minEdgeValue with this value and
  // update the answer variable to the edge being examined.

  // after every visited node has been similarly processed, return the answer variable

}

    private void mst(int startingNode) {
        // initial MST has no edges
        for (int r = 0; r < mstMatrix.length; r++) {
            for (int c = 0; c < mstMatrix.length; c++) {
                mstMatrix[r][c] = -1;
            }
        }

        // add the starting node to the visited set

       // write code here  to add another edge/node to the MST by calling the nextEdgeToVisit method to find out
      // which edge to add next

       //  add the node you just added to the MST, to the visited set
     
//  keep going until all the nodes have been visited  (until nextEdgeToVisit returns a null)
        }
    }

    // the printMatrix method is used to print the final solution
    // it is also useful for debugging
    public static void printMatrix(int[][] a) {
        for (int r = 0; r < a.length; r++) {
            for (int c = 0; c < a.length; c++) {
                String item = a[r][c] == -1 ? "-" : a[r][c] +"";
                System.out.printf("%2s ", item);
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {

        int [][] matrix = {

                //A B  C  D  E  F  G  H  I

                {-1, 7,-1,-1,-1,-1,-1,-1,15},

                { 7,-1, 5,-1,-1,-1,-1,-1,-1},

                {-1, 5,-1, 4, 2,-1, 3,-1,-1},

                {-1,-1, 4,-1, 1, 9,-1,-1,-1},

                {-1,-1, 2, 1,-1,-1,-1,-1,-1},

                {-1,-1,-1, 9,-1,-1, 5,12,-1},

                {-1,-1, 3,-1,-1, 5,-1,-1, 6},

                {-1,-1,-1,-1,-1,12,-1,-1,10},

                {15,-1,-1,-1,-1,-1, 6,10,-1}

        };

        Prims p = new Prims(matrix);
        p.mst(0);
        printMatrix(p.matrix);           // print the original  graph
        printMatrix(p.mstMatrix);     // print  the MST
    }
}