Prim's Algorithm: Growing a Minimum Spanning Tree
Learn Prim's algorithm for finding minimum spanning trees starting from a vertex, using a greedy approach with priority queues.
Prim’s Algorithm: Growing a Minimum Spanning Tree
Like Kruskal’s, Prim’s algorithm finds a Minimum Spanning Tree—but it grows a single tree from a chosen starting vertex rather than building a forest. At each step, Prim’s adds the cheapest edge that connects the current tree to an outside vertex. This “growing tree” approach makes Prim’s particularly natural for dense graphs and those represented as adjacency matrices.
The algorithm maintains a priority queue of edges crossing the cut between visited and unvisited vertices, always picking the minimum-weight crossing edge.
Introduction
Prim’s algorithm grows a Minimum Spanning Tree incrementally from a chosen starting vertex, always adding the cheapest edge that connects the current tree to an unvisited vertex. Unlike Kruskal’s which builds a forest by considering all edges globally, Prim’s builds a single tree—this “growing tree” paradigm feels natural for problems where you start from a specific root and expand outward. The algorithm exemplifies the greedy paradigm applied to spanning trees, relying on the cut property that guarantees the minimum crossing edge always belongs to some MST.
Prim’s matters in network design, clustering, and image segmentation where you need to grow connected structures from a seed point. The choice between Prim’s and Kruskal’s depends on graph representation: Prim’s with a priority queue runs in O(E log V) and works well with adjacency lists, while the O(V²) matrix implementation outperforms heap-based approaches on dense graphs. Both algorithms produce identical MST weight—only the construction path differs.
This guide covers the heap-based and matrix-based implementations, shows how to detect disconnected graphs, and compares Prim’s against Kruskal’s and against Dijkstra’s algorithm. You’ll also understand the cut property that makes greedy MST algorithms correct.
Basic Implementation
import heapq
from collections import defaultdict
def prim_mst(graph, start=0):
"""
Prim's algorithm for Minimum Spanning Tree.
Args:
graph: Adjacency list {u: [(v, weight), ...]}
start: Starting vertex
Returns:
(mst_edges, total_weight) tuple
"""
n = len(graph)
visited = [False] * n
min_heap = [] # (weight, u, v)
visited[start] = True
# Add all edges from start vertex
for neighbor, weight in graph[start]:
heapq.heappush(min_heap, (weight, start, neighbor))
mst_edges = []
total_weight = 0
while min_heap and len(mst_edges) < n - 1:
weight, u, v = heapq.heappop(min_heap)
if visited[v]:
continue # Skip if already in MST
# Add edge to MST
mst_edges.append((u, v, weight))
total_weight += weight
visited[v] = True
# Add edges from newly added vertex
for neighbor, w in graph[v]:
if not visited[neighbor]:
heapq.heappush(min_heap, (w, v, neighbor))
if len(mst_edges) != n - 1:
return [], float('inf') # Graph is disconnected
return mst_edges, total_weightDense Graph Implementation
For dense graphs where E ≈ V², a O(V²) adjacency matrix implementation beats heap-based approaches:
def prim_mst_dense(num_vertices, graph):
"""
Prim's algorithm with O(V²) using adjacency matrix.
Better for dense graphs.
Args:
num_vertices: Number of vertices
graph: num_vertices x num_vertices matrix where graph[i][j] = weight
"""
in_mst = [False] * num_vertices
min_edge = [float('inf')] * num_vertices
parent = [-1] * num_vertices
# Start from vertex 0
min_edge[0] = 0
for _ in range(num_vertices):
# Find minimum vertex not yet in MST
u = -1
min_weight = float('inf')
for v in range(num_vertices):
if not in_mst[v] and min_edge[v] < min_weight:
min_weight = min_edge[v]
u = v
if u == -1:
break # Graph is disconnected
in_mst[u] = True
if parent[u] != -1:
# Add edge to MST
pass # Edge (parent[u], u) is in MST
# Update minimum edges for adjacent vertices
for v in range(num_vertices):
if not in_mst[v] and graph[u][v] < min_edge[v]:
min_edge[v] = graph[u][v]
parent[v] = u
# Compute total weight
total = sum(min_edge[i] for i in range(num_vertices))
return parent, totalWhen to Use Prim’s Algorithm
Use Prim’s when:
- You need a Minimum Spanning Tree from a specific starting point
- Graph is dense (adjacency matrix representation)
- You want a single tree rather than a forest
- You need to grow the tree incrementally
Don’t use Prim’s when:
- Graph is very sparse (Kruskal’s with union-find is often faster)
- Graph is disconnected (Kruskal’s naturally produces a forest)
- You only need approximate MST (though both are exact)
Trade-off Analysis
| Aspect | Prim’s (Heap) | Prim’s (Matrix) | Kruskal’s |
|---|---|---|---|
| Time (Sparse) | O((V+E) log V) | O(V²) | O(E log E) |
| Time (Dense) | O(E log V) | O(V²) | O(E log E) ≈ O(V² log V) |
| Space | O(V + E) | O(V²) | O(V + E) |
| Natural For | Incremental growth | Dense graphs | Simple implementation |
Production Failure Scenarios
- Disconnected graph: Prim’s will only visit vertices reachable from start, returning an incomplete tree—detect this by checking if all vertices were visited
- Large dense graphs: O(V²) memory for adjacency matrix can be prohibitive—use adjacency list with heap
- Integer overflow: When summing edge weights, ensure appropriate data types
Complete Example
def solve():
# Example graph as adjacency list
graph = {
0: [(1, 10), (3, 5)],
1: [(0, 10), (2, 1), (3, 3)],
2: [(1, 1), (3, 9), (4, 4)],
3: [(0, 5), (1, 3), (2, 9), (4, 2)],
4: [(2, 4), (3, 2)]
}
mst, weight = prim_mst(graph, start=0)
print(f"MST total weight: {weight}")
print("Edges in MST:")
for u, v, w in mst:
print(f" {u} -- {v}: {w}")Quick Recap Checklist
- Start from any vertex (or specified start)
- Maintain priority queue of crossing edges
- Always add minimum-weight edge connecting visited to unvisited
- Continue until V-1 edges or queue empty
- Check for disconnected graph (incomplete MST)
- Choose heap for sparse, matrix for dense graphs
Interview Questions
A cut separates vertices into two non-empty sets. The cut property states: for any cut, the minimum-weight edge crossing that cut belongs to some minimum spanning tree. Prim's repeatedly applies this by maintaining a cut between visited and unvisited vertices—at each step, the minimum crossing edge must be in the MST, so adding it is always safe.
Prim's and Dijkstra's look identical in implementation but differ fundamentally in goal. Both use a priority queue to pick minimum-weight crossing edges. Dijkstra's selects the minimum-distance vertex from source and accumulates path distances. Prim's selects the minimum crossing edge to any unvisited vertex regardless of source. The difference: Prim's doesn't accumulate distances or care about which vertex you started from—it's building a tree that spans all vertices.
Yes—and it will always produce the same total MST weight regardless of start vertex. The resulting set of edges might be ordered differently or have different intermediate structures, but the sum of all edge weights will be identical. This is because all MSTs for a given graph have the same total weight (the MST is unique in weight, though not necessarily in structure if multiple edges have equal weights).
Choose Prim's for dense graphs where E ≈ V²—the O(V²) matrix implementation avoids heap overhead. Choose Kruskal's for sparse graphs where E << V²—its O(E log E) sorting dominates. Also prefer Prim's when you need a tree rooted at a specific vertex, or when your graph is naturally represented as an adjacency matrix rather than an edge list.
The time complexity depends on the data structure used for the priority queue:
- Binary Heap: O((V + E) log V) — most common implementation
- Fibonacci Heap: O(E + V log V) — theoretically better for dense graphs
- Adjacency Matrix (no heap): O(V²) — best for dense graphs where E ≈ V²
- Unsorted Array: O(V²) — simple but slow for large graphs
Yes. Unlike Dijkstra's algorithm, which fails with negative edge weights, Prim's algorithm works correctly with negative weights. The cut property still holds: the minimum-weight edge crossing any cut belongs to some MST, regardless of whether the weights are negative or positive. However, if the graph has a negative-weight cycle, the concept of a minimum spanning tree isn't well-defined, but Prim's will still produce a valid spanning tree.
After Prim's finishes, check the number of edges collected. If the graph has V vertices and Prim's collects fewer than V - 1 edges, the graph is disconnected. The algorithm only visits vertices reachable from the starting vertex. To handle this in code:
- Track the visited count and compare to the total vertex count
- If
len(mst_edges) != n - 1, return an error or infinite weight - Alternatively, run a DFS/BFS from the start vertex first to check connectivity
Prim's algorithm is used in various real-world applications:
- Network design: Laying fiber-optic cable, electrical grids, or water pipes at minimum cost while connecting all nodes
- Transportation: Building roads or railway networks connecting cities with minimum total construction cost
- Cluster analysis: Constructing minimum spanning trees for hierarchical clustering
- Approximation algorithms: Used as a subroutine in approximation algorithms for NP-hard problems like the Traveling Salesman Problem
Both versions follow the same greedy principle but differ in how they manage the priority queue:
- Lazy Prim's: Pushes all crossing edges onto the heap without removing stale entries. When popping, it skips edges leading to already-visited vertices. Simpler to implement but the heap can grow to O(E) size.
- Eager Prim's: Maintains a fixed-size array of best-known distances and supports decrease-key operations. Only the best edge to each unvisited vertex is kept in the priority queue, keeping heap size at O(V). Requires a data structure that supports decrease-key efficiently.
Prim's algorithm is designed for undirected graphs because it relies on the cut property, which assumes edges are symmetric. In a directed graph, the minimum-weight edge crossing a cut might not be usable in both directions when building a tree. Finding a minimum spanning arborescence (the directed equivalent) requires a different algorithm, such as Edmonds' algorithm (Chu–Liu/Edmonds).
The starting vertex does not affect the final MST weight—all spanning trees for a connected graph have the same total weight. However, it does affect intermediate steps: the order in which vertices join the tree, the contents of the priority queue at each step, and the exact edges selected. In dense graphs with multiple equal-weight edges, different starting points can produce structurally different MSTs while maintaining the same total weight.
Yes, Prim's is naturally iterative—the priority queue loop is the core, not recursion. There's no need for recursive calls since the algorithm repeatedly extracts the minimum crossing edge until the MST is complete. Watch out for stack overflow in recursive implementations of other graph algorithms (like DFS), but Prim's main loop is straightforward iteration. The only consideration is ensuring the heap operations (push/pop) are correctly managed.
To find a maximum spanning tree, simply reverse the comparison in the priority queue—instead of always extracting the minimum crossing edge, extract the maximum. This means using a max-heap, or equivalently, negating all edge weights and using a min-heap. The cut property still holds for maximums: the maximum-weight edge crossing any cut belongs to some maximum spanning tree. This modification is trivial and often used in network design where maximum reliability or bandwidth matters.
The visited array tracks which vertices have been added to the MST, enforcing the cut between visited (in the tree) and unvisited (outside the tree) sets. Without it, the algorithm might select edges that connect two vertices already in the MST, violating the tree property. When popping an edge from the heap, you check if visited[v]: continue to skip stale entries in lazy Prim's. This array is also used to detect disconnected graphs—if fewer than V-1 edges are added, not all vertices were reachable.
BFS and DFS are uninformed traversals—they explore vertices based on discovery order rather than edge weights. Prim's is a weighted traversal: it always picks the minimum-weight crossing edge, making it a greedy algorithm with a specific optimization goal (minimum spanning tree). BFS finds shortest paths in unweighted graphs; Prim's finds minimum-cost trees in weighted graphs. Both maintain visited sets, but Prim's uses a priority queue where DFS uses a stack and BFS uses a queue.
Lazy Prim's is simpler and can outperform eager Prim's when:
- Memory is constrained—lazy Prim's uses the heap more intensively but avoids the overhead of maintaining a decrease-key data structure
- Graph is sparse—the O(E) heap size is manageable and the simpler implementation has lower constant factors
- Edge weights are large—many stale entries may exist, but the simplicity of lazy deletion often wins over complex eager bookkeeping
Eager Prim's wins when heap size matters significantly or when decrease-key operations are cheap (e.g., Fibonacci heaps).
To find a minimum spanning forest (one MST per component), run Prim's starting from an unvisited vertex whenever the algorithm completes without spanning all vertices. The adaptation: after each run completes, scan the visited array for any False entries and start a new Prim's from the first unvisited vertex. Each iteration builds a separate spanning tree. This is essentially what Kruskal's does implicitly—it naturally produces a forest when the graph is disconnected.
For large graphs, several optimizations help:
- Adjacency list over matrix—O(V+E) vs O(V²) space, critical for sparse graphs with millions of vertices
- Lazy Prim's heap pruning—skip stale entries with visited checks instead of maintaining exact entries
- Bit arrays for visited—use Python's
bytearrayorarray('b')for compact visited tracking - Streaming edge reads—for graphs too large to fit in memory, read edges in batches and process incrementally
Prim's handles parallel edges correctly—both edges will be pushed to the heap, and the algorithm will naturally pick the lighter one when its endpoint becomes reachable. The presence of parallel edges doesn't break correctness; it just means the heap may contain multiple entries for the same vertex pair. The visited check ensures only one edge per vertex join is used in the final MST. Ensure your graph representation distinguishes parallel edges (e.g., keep multiple weight entries in the adjacency list).
Yes—a minimum spanning forest is simply multiple MSTs for disconnected graph components. Run Prim's normally; if it finishes with fewer than V-1 edges, the graph was disconnected. To find the full forest, track visited vertices and when the algorithm ends, find the first unvisited vertex, start a new Prim's from there, and repeat until all vertices are covered. Each run produces one component's MST. This approach is equivalent to running Kruskal's on a disconnected graph—the result is a forest rather than a single tree.
Further Reading
- CLRS Introduction to Algorithms (Chapter 23) – Covers Prim’s and Kruskal’s with rigorous proofs of the cut property and optimal substructure for minimum spanning trees.
- The Algorithm Design Manual by Steven Skiena – Offers practical guidance on selecting between Prim’s and Kruskal’s with real-world graph examples.
- Priority Queues and Binary Heaps – Understanding heap operations is essential for analyzing Prim’s O((V+E) log V) time complexity.
- Fibonacci Heaps – For advanced readers, Prim’s achieves O(E + V log V) with Fibonacci heaps, the theoretical best for sparse graphs.
- Adjacency Matrix vs Adjacency List – How the choice of graph representation affects Prim’s performance and memory footprint.
- Related Content:
Conclusion
Prim’s algorithm grows an MST one vertex at a time, always adding the cheapest edge from the visited set to an unvisited vertex. Use the heap version for sparse graphs and the O(V²) matrix version for dense ones. Like Kruskal’s, it relies on the cut property—each minimum crossing edge is always safe to add.
Category
Related Posts
Kruskal's Algorithm: Building Minimum Spanning Trees
Learn Kruskal's algorithm for finding minimum spanning trees in weighted graphs using union-find data structures.
Bellman-Ford Algorithm: Shortest Paths with Negative Weights
Learn the Bellman-Ford algorithm for single-source shortest paths including negative edge weights and negative cycle detection.
Dijkstra's Algorithm: Finding Shortest Paths in Weighted Graphs
Master Dijkstra's algorithm for single-source shortest path problems in weighted graphs with positive edges, including implementations and trade-offs.