1. One-Liner
Prim builds an MST by starting at an arbitrary root and repeatedly attaching the minimum-weight edge that connects the growing tree to a new vertex.
2. The Problem It Solves
Find a minimum spanning tree: connect all vertices with V−1 edges minimizing total weight — used in network design, clustering, approximation.
3. The Core Idea
Cut property: the lightest edge crossing any cut between tree and non-tree is safe for MST. Prim always picks the lightest edge from the current tree to outside.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Start with any vertex in MST set; key[v]=min edge weight to tree |
| 2 | Min-heap: extract min key vertex u not in tree |
| 3 | For each edge (u,v,w): if v not in tree and w < key[v], update |
| 4 | Repeat until V−1 edges or heap empty |
| 5 | parent[] stores MST edges |
5. Dry Run Example
Square 0—1 (1), 1—2 (2), 2—3 (3), 3—0 (4), diagonals costly. Prim from 0 picks 0–1, then 1–2, then 2–3 — total 6.
6. Key Properties
| Property | Value |
|---|---|
| Works on | Connected undirected weighted graphs |
| Greedy | Yes — cut property |
| Fibonacci heap | Theoretical O(E + V log V) |
7. Where It Is Used
| Domain | Use |
|---|---|
| Network design | Min-cost fiber layout |
| Approximation | TSP heuristics building blocks |
8. Interview Tips
Compare Prim vs Kruskal (node-centric vs edge-centric). Dense graphs prefer Prim with adjacency matrix O(V²).
9. Comparison with Other Algorithms
| Prim | Kruskal | |
|---|---|---|
| View | Grow one tree | Sort all edges |
| Best | Dense | Sparse (union-find) |
| Data | Heap | Sort + DSU |
10. Complexity
| -- | -- |
|---|---|
| Time | O((V+E) log V) with binary heap |
| Space | O(V + E) |
Implementation Example (PYTHON)
import heapq
def prim(n, edges):
g = [[] for _ in range(n)]
for u, v, w in edges:
g[u].append((v, w)); g[v].append((u, w))
in_mst = [False] * n
pq = [(0, 0)]
total = 0
while pq:
w, u = heapq.heappop(pq)
if in_mst[u]: continue
in_mst[u] = True
total += w
for v, wt in g[u]:
if not in_mst[v]:
heapq.heappush(pq, (wt, v))
return total