Prim's Java Code

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

@AllArgsConstructor
class Edge implements {
    // vertex
    int to;
    // weight
    int w;
}

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

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

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

        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e->e.w));

        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.
        key[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
                    pq.remove (k[v]);
                    k[v].w = g[u][v];
                    pq.add (k[v]);

                    // 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]);
        }
    }
}