Prim's Minimum Spanning Tree (Cheapest Way to Connect Every Node)

• Minimum spanning tree (MST) – a subset of edges connecting all vertices with the smallest total weight.
• Prim's algorithm – grows one tree outward from a starting vertex, always adding the cheapest edge to a vertex not yet in the tree.
• Min-heap – stores candidate edges keyed by weight; the cheapest frontier edge is always at the top.
• Lazy variant – uses a plain heap and discards stale entries (edges to already-included vertices).
• Cut property – for any partition of vertices, the cheapest crossing edge belongs to some MST, justifying the greedy step.
• Complexity – O(E log V) time with a binary heap.

What is a minimum spanning tree?

A minimum spanning tree (MST) of a connected weighted undirected graph is a subset of edges that connects all vertices with the smallest possible total weight. It contains exactly V-1 edges (where V is the number of vertices) and forms a tree (no cycles). There may be multiple MSTs if some edge weights are equal.

package com.bank.model;

import java.util.ArrayList;
import java.util.List;

public class BranchGraph {
    private final int vertices;
    private final List<List<int[]>> adj; // adj[u] = list of {v, weight}

    public BranchGraph(int vertices) {
        this.vertices = vertices;
        this.adj = new ArrayList<>();
        for (int i = 0; i < vertices; i++) adj.add(new ArrayList<>());
    }

    public void addEdge(int u, int v, int weight) {
        adj.get(u).add(new int[]{v, weight});
        adj.get(v).add(new int[]{u, weight});
    }

    public int getVertices() { return vertices; }
    public List<int[]> neighbors(int u) { return adj.get(u); }
}

How does Prim's algorithm work?

Start from any vertex. Mark it as in the tree. Push all its edges into a min-heap keyed by weight. Repeatedly pop the cheapest edge. If its destination is already in the tree, skip it. Otherwise, add the destination to the tree, add the edge weight to the total, and push all edges from the new vertex to vertices not yet in the tree.

package com.bank.service;

import com.bank.model.BranchGraph;
import java.util.PriorityQueue;

public class PrimMST {
    public static int minimumCost(BranchGraph graph) {
        int v = graph.getVertices();
        boolean[] inTree = new boolean[v];
        // heap entries: {weight, vertex}
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        heap.offer(new int[]{0, 0}); // start from vertex 0
        int totalCost = 0;
        int edgesUsed = 0;

        while (!heap.isEmpty() && edgesUsed < v) {
            int[] top = heap.poll();
            int weight = top[0];
            int node = top[1];

            if (inTree[node]) continue; // skip stale entry

            inTree[node] = true;
            totalCost += weight;
            edgesUsed++;

            for (int[] edge : graph.neighbors(node)) {
                if (!inTree[edge[0]]) {
                    heap.offer(new int[]{edge[1], edge[0]});
                }
            }
        }
        return totalCost;
    }

    public static void main(String[] args) {
        // 4 branches: HDFC(0), ICICI(1), SBI(2), PNB(3)
        BranchGraph g = new BranchGraph(4);
        g.addEdge(0, 1, 10); // HDFC-ICICI: cost 10
        g.addEdge(0, 2, 6);  // HDFC-SBI: cost 6
        g.addEdge(0, 3, 5);  // HDFC-PNB: cost 5
        g.addEdge(1, 3, 15); // ICICI-PNB: cost 15
        g.addEdge(2, 3, 4);  // SBI-PNB: cost 4

        System.out.println("Minimum network cost: " + minimumCost(g));
    }
}

Minimum network cost: 19

Why is the greedy choice correct (cut property)?

The cut property states: for any partition of vertices into two sets S and V-S, the lightest edge crossing the partition belongs to some MST. Prim's always picks the cheapest edge from the tree vertices (S) to the non-tree vertices (V-S), which is exactly this lightest crossing edge. So each step is provably safe.

Cut Property:
  S = {vertices in tree}
  V-S = {vertices not in tree}
  Cheapest edge crossing the cut → belongs to some MST
  Prim's picks exactly this edge at each step

What is the lazy vs eager variant?

The lazy variant pushes all candidate edges into the heap and discards stale ones (edges to already-included vertices) when they are popped. The eager variant uses an indexed priority queue with decrease-key to update existing entries, so the heap never contains stale entries. Both are O(E log V) but the eager variant has tighter constants.

| Variant | Heap Size | Decrease-Key | Time |
|---|---|---|---|
| Lazy (binary heap) | Up to E entries | Not needed | O(E log V) |
| Eager (indexed PQ) | At most V entries | Yes | O(E log V) |

// Lazy: skip stale entries
if (inTree[node]) continue;

// Eager: would update the key in the indexed PQ instead of adding duplicates
// indexedPQ.decreaseKey(node, weight);

How is Prim's different from Kruskal's?

Prim's grows one tree from a starting vertex. Kruskal's sorts all edges by weight and adds them one by one, skipping edges that would create a cycle (using Union-Find). Prim's is preferred for dense graphs; Kruskal's for sparse graphs.

| Feature | Prim's | Kruskal's |
|---|---|---|
| Approach | Grow one tree | Sort all edges, add safe ones |
| Data structure | Min-heap | Sorted edges + Union-Find |
| Better for | Dense graphs | Sparse graphs |
| Time | O(E log V) | O(E log E) |

// Kruskal's approach (contrast)
// Sort edges by weight
// For each edge, if union(u,v) succeeds (different sets), add to MST

What are the edge cases?

Single vertex (MST cost is 0), disconnected graph (MST does not exist), and a graph where all edge weights are equal (any spanning tree is minimum).

package com.bank.service;

import com.bank.model.BranchGraph;

public class PrimEdgeCases {
    public static void main(String[] args) {
        // Single vertex
        BranchGraph single = new BranchGraph(1);
        System.out.println("Single vertex: " + PrimMST.minimumCost(single));

        // Triangle with equal weights
        BranchGraph equal = new BranchGraph(3);
        equal.addEdge(0, 1, 5);
        equal.addEdge(1, 2, 5);
        equal.addEdge(0, 2, 5);
        System.out.println("Equal weights: " + PrimMST.minimumCost(equal));
    }
}

Single vertex: 0
Equal weights: 10

What is the time and space complexity?

With a binary heap, each edge is inserted and possibly extracted once, giving O(E log V) time. Space is O(V + E) for the adjacency list, the heap, and the inTree array.

What should a senior engineer know?

A senior engineer should understand the cut property proof, the lazy vs eager tradeoff, and when to use Prim's versus Kruskal's. In production at National Bank of India, Prim's plans the cheapest leased-line network connecting all branches.

// Production usage: minimum cost network
BranchGraph network = loadBranchNetwork();
int cost = PrimMST.minimumCost(network);
System.out.println("Annual leased-line budget: " + cost + " lakhs");