Prim’s algorithm builds a Minimum Spanning Tree — the cheapest set of edges that connects every vertex — by growing a single tree outward. It starts at any vertex and repeatedly adds the cheapest edge connecting the tree to a vertex outside it.

Like a vine creeping across a network, the tree expands one vertex at a time.

Structurally it is a close cousin of Dijkstra: same priority queue, same relax-style loop, but a different objective — cheapest edge in, not cheapest path from source.

How It Works

1. Initialize: set key[start] = 0, all others ∞; parent null; insert all vertices into a priority queue.
2. Extract min: remove the vertex with the smallest key — the cheapest one not yet in the tree.
3. Relax neighbors: for each unvisited neighbor, if the edge weight is less than its current key, update the key and set the parent.
4. Repeat: until the queue is empty. The parent pointers now define the MST edges.

Key Insight

Correctness rests on the cut property: for any partition of vertices into “in the tree” and “not in the tree,” the minimum-weight edge crossing that cut belongs to some MST.

Prim’s applies the property at every step — each new vertex is pulled in across the cheapest available crossing edge — so the final tree is globally minimal.

The key values are “cheapest edge connecting this vertex to the tree so far,” which is exactly what gets relaxed as the tree grows.

Worked Example

Run Prim’s on the visualizer’s MST graph starting at A:

• Tree {A}: cheapest crossing edge is A–C (2) → add C.
• Tree {A, C}: crossing edges: A–B(4), A–D(6), C–D(1), C–F(3) → cheapest is C–D (1) → add D.
• Tree {A, C, D}: crossing edges: D–B(3), D–F(4), D–E(2), A–B(4), A–D(6) → cheapest is D–E (2) → add E.
• Tree {A, C, D, E}: crossing edges: D–B(3), D–F(4), E–B(5), E–F(6) → cheapest is D–B (3) → add B.
• Tree {A, B, C, D, E}: crossing edges: D–F(4), E–F(6) → cheapest is D–F… but C–F(3) is also crossing → cheapest is C–F (3) → add F.

MST edges: A–C, C–D, D–E, D–B, C–F, total weight 2+1+2+3+3 = 11. Watch the visualizer grow the tree one vertex at a time, always via the cheapest frontier edge.

Edge Cases & Pitfalls

• Disconnected graph — Prim’s never reaches vertices in other components: it produces a spanning tree of only the start’s component. Pre-check connectivity if you need a full MST.
• Equal weights — multiple MSTs exist; Prim’s returns one of them depending on tie-breaking order.
• Directed graphs — MST is an undirected concept: Prim’s assumes undirected edges.
• Dense graphs — with an array-based min-key scan instead of a heap, Prim’s runs in O(V²), faster than the heap version when E is near V².

Comparison: Prim vs Kruskal

Applications

• Network design — laying cable, fiber, or pipelines at minimum cost
• Circuit design — minimizing wire length on a chip
• Clustering — MST-based natural groupings
• Approximation algorithms — MST bounds for TSP

Practice Trajectory

1. Hand-trace Prim’s from vertex B on the visualizer graph and compute the MST weight.
2. State the cut property and explain how each Prim step applies it.
3. Contrast the relax loop with Dijkstra’s and identify the single difference.
4. Determine when the O(V²) array-based Prim beats the heap version.
5. Implement Prim’s with a priority queue and confirm the MST weight matches Kruskal’s.