Graphs

Graph Patterns: Minimum Spanning Tree (Prim's Algorithm)

May 2026

7 min read

When tasked with connecting all computers in a network or laying down fiber optic cables to all cities at the absolute minimum cost, you are looking for a Minimum Spanning Tree (MST).

Introduction

A Spanning Tree is a subgraph that connects all the vertices together without any cycles. A Minimum Spanning Tree (MST) is the spanning tree whose sum of edge weights is as small as possible.

Prim's Algorithm is a beautiful greedy approach to building an MST.

The Greedy Strategy

We start at an arbitrary node and add it to our "Tree". Then, we look at all the outgoing edges from our current Tree to unvisited nodes. We greedily pick the absolute cheapest edge available, add that new node to our Tree, and repeat.

By utilizing a Min-Heap (Priority Queue), we can effortlessly track the cheapest available boundary edges. Every time we add a node to the MST, we simply dump all of its outgoing edges into the Min-Heap.

Implementation

java

class Solution {
    public int spanningTree(int V, ArrayList<ArrayList<int[]>> adj) {
        // Min-Heap: {weight, node}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        boolean[] vis = new boolean[V];
        
        // Start from node 0 with 0 weight
        pq.add(new int[]{0, 0});
        int sum = 0;
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int wt = current[0];
            int node = current[1];
            
            // If already part of the MST, skip
            if (vis[node]) continue;
            
            // Mark as visited and add weight to total cost
            vis[node] = true;
            sum += wt;
            
            // Push all unvisited neighbors into the priority queue
            for (int[] edge : adj.get(node)) {
                int neighbor = edge[0];
                int edgeWeight = edge[1];
                
                if (!vis[neighbor]) {
                    pq.add(new int[]{edgeWeight, neighbor});
                }
            }
        }
        return sum;
    }
}