Prim's Java Code

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

@AllArgsConstructor
class Edge implements Comparable<Edge> {
    // vertex
    int v;
    // weight
    int w;
   
    @Override
    public int compareTo(Edge other) {
        return this.w - other.w;
    }
}

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

        boolean[] inMST = new boolean[n];

        // key, currently smallest weight that connects i to MST
        Edge[] k = new Edge[n];

        // stores the parent vertex for each entry
        int[] parent = new int[n]

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

        for (int i = 0; i < n; i++) {
            // set to max because i is not connected to the MST yet
            key[i] = new Edge(i, Integer.MAX_VALUE);
            pq.add(key[i]);
            parent [i] = -1;
        }

        // set to 0 because since we picked this to start, he is the MST
        key[0].weight = 0;

        pq.add(new Edge(0,0));

        while (!pq.isEmpty()) {
            int u = pq.poll().v;
            inMST[u] = true;

            for (int v = 0; v < n; v++) {
                if (g[u][v] != 0 && !inMST[v] && graph[u][v] < k[v].w) {
                    // there is a edge connecting u,v
                    // v is not in the MST
                    // (u,v).w is smaller than the minimum weight we found connecting v to the MST
                    pq.remove (key[v]);
                    key[v].w = graph[u][v];
                    pq.add (key[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]);
        }
    }
}