Prim's MST | Graph Patterns

🌐

Prim's Minimum Spanning Tree

Grow MST greedily — always add the cheapest edge connecting the tree to an unvisited node

MSTMin-Heap GreedyUndirected Weighted Graph

Time: O(E log V) Space: O(V + E)

When to Use

Find minimum cost to connect all nodes in a weighted graph
Network/cable layout problems — minimize total wire cost
Cluster analysis — connect nearest clusters
Approximation for TSP (Travelling Salesman)
Dense graphs (Prim's often better than Kruskal's for dense)

Complexity

With binary heap	O(E log V)
With Fibonacci heap	O(E + V log V)
Simple array	O(V²) — for dense graphs
MST edges	Always exactly V−1 edges

Problem Given 5 points (nodes 0–4) connected by weighted undirected edges, find the minimum cost to connect all points (Minimum Spanning Tree). Prim's algorithm greedily picks the cheapest edge to any unvisited node using a min-heap — same PQ pattern as Dijkstra but minimises total tree weight, not path distances.
Input: 5 nodes, edges: 0–1(2), 0–3(6), 1–2(3), 1–3(8), 1–4(5), 2–4(7) · Answer: MST = 0–1(2) + 1–2(3) + 1–4(5) + 0–3(6) = 16

MST Total Cost: 0

🌿 MST Edges Added

none yet

⛏ Priority Queue (w, to, from)

Step 0 / 7

Init Pop Min Add to MST Skip Visited Done

Initialize: push (weight=0, node=0, from=-1) into min-heap. Start from node 0.

pq.offer(new int[]{0, 0}); // {weight, node}

Java Pattern Template skeleton only

// Prim's MST — grow tree by always picking cheapest edge (pattern skeleton)
boolean[] inMST = new boolean[n];
// min-heap: [weight, node]
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0]-b[0]);
pq.offer(new int[]{0, 0}); // start from node 0, cost 0
int totalCost = 0;

while (!pq.isEmpty()) {
    int[] cur = pq.poll();
    int w = cur[0], u = cur[1];
    if (inMST[u]) continue; // already in MST — stale entry
    inMST[u] = true;
    totalCost += w;
    for (int[] e : adj.get(u)) { // e = [neighbor, weight]
        int v = e[0], ew = e[1];
        if (!inMST[v]) pq.offer(new int[]{ew, v});
    }
}
// totalCost = MST weight. If MST has < n-1 edges → disconnected graph.

🎯 Practice Problems

#1584 Min Cost to Connect Points M #1135 Connecting Cities Min Cost M #1168 Optimize Water Distribution H GFG Minimum Spanning Tree M