LOG_ENTRY // Graphs

GreedySpanning:
ImplementingPrim'sAlgorithm

Apr 2026 10 min read

Prim's algorithm is a greedy masterpiece. It builds a Minimum Spanning Tree by always picking the cheapest edge that connects the current tree to an outside node.

SOURCE_MANIFEST

class Solution {
    static int spanningTree(int V, List<List<int[]>> adj) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        boolean[] vis = new boolean[V];
        pq.add(new int[]{0, 0});
        int sum = 0;

        while (!pq.isEmpty()) {
            int[] it = pq.poll();
            int wt = it[0];
            int node = it[1];

            if (vis[node]) continue;
            vis[node] = true;
            sum += wt;

            for (int[] neighbor : adj.get(node)) {
                if (!vis[neighbor[0]]) {
                    pq.add(new int[]{neighbor[1], neighbor[0]});
                }
            }
        }
        return sum;
    }
}