Prim's Java Code

MSP

import java.util.*;
import lombok.AllArgsConstructor;

@AllArgsConstructor
class Edge implements Comparable<Edge> {
    // vertex
    int to;
    // weight
    int w;

    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.w, other.w);
    }
}

public class Prim 
{
    // g is the adjacency matrix
    public void primMST(int[][] g) {
        int n = g.length;

        // inMST[v] true if v is in MST
        boolean[] inMST = new boolean[n]; 
        // k[i] smallest edge from i to MST
        Edge[] k = new Edge[n]; 

        // stores the parent vertex for each entry
        // parent[v] is the vertex connected to v by the edge in the MST, can be followed to reach the root of the MST
        int[] parent = new int[n]; 

        PriorityQueue<Edge> pq = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            // each i is not connected to MST yet
            k[i] = new Edge(i, Integer.MAX_VALUE); 
            parent [i] = -1;
        }

        // we pick 0 as root.
        k[0].w = 0;
        pq.add (k[0]);

        while (!pq.isEmpty()) {
            int u = pq.poll().to;

            if (inMST[u]) continue;
            inMST[u] = true;

            for (int v = 0; v < n; v++) {
                if (g[u][v] != 0 && !inMST[v] && g[u][v] < k[v].w) {
                    // there is a edge connecting u,v
                    // v is not in the MST
                    // (u,v).w smaller than minW found connecting v to the MST
                    k[v].w = g[u][v];
                    pq.add (new Edge(v, k[v].w));

                    // mst now contains the edge (u,v)
                    parent[v] = u;
                }
            }
        }
        printMST (parent, g);
    }

    public void printMST(int[] parent, int[][] g) {
        System.out.println("Edge \tweight");
        for (int i = 1; i < g.length; i++) {
            System.out.println (parent[i] + " - " + i + "\t" + g[i][parent[i]]);
        }
    }
}