What is Prim's Algorithm?
Learn how Prim's algorithm grows a minimum spanning tree using a min-heap, with mechanism, code example, and interview answer.
Expected Interview Answer
Prim's algorithm builds a minimum spanning tree by growing a single connected tree from an arbitrary start vertex, at each step adding the cheapest edge that connects a vertex already in the tree to a vertex not yet in it, typically using a min-heap to pick that cheapest edge in O(log V) time.
The algorithm starts with one vertex in the tree and all its edges as candidates in a priority queue keyed by weight. It repeatedly pops the cheapest candidate edge; if the far endpoint is already in the tree the edge is discarded as it would form a cycle, otherwise the edge is added to the MST and the newly included vertex's outgoing edges are pushed onto the priority queue as new candidates. This continues until all V vertices are in the tree, giving O(E log V) time with a binary heap and adjacency list, which makes Prim's especially efficient on dense graphs when implemented with an adjacency matrix and simple array scan in O(V^2). Unlike Kruskal's, which considers edges globally sorted by weight, Prim's always grows one connected frontier, which is why it is often preferred when the graph is given as an adjacency matrix or when a streaming/incremental spanning tree is needed.
- Grows one connected tree, never needs global sorting of all edges
- O(E log V) with a binary heap, or O(V^2) on dense adjacency-matrix graphs
- Naturally incremental — useful when vertices are discovered progressively
- Guarantees a minimum-weight spanning tree, same guarantee as Kruskal's
AI Mentor Explanation
A regional academy network starts with a single home academy and grows outward one link at a time, always picking the cheapest coaching-exchange link from any academy currently in the network to any academy not yet joined. Once that cheapest link is added, the newly joined academy's own outward links become new candidates, and the process repeats, always choosing the single cheapest frontier link available. This keeps the growing network connected at every step, never splitting into separate pieces, unlike an approach that considers links anywhere on the map. Once every academy has joined through its cheapest connecting link, the total link cost is guaranteed minimal for a fully connected network.
Step-by-Step Explanation
Step 1
Start with one vertex
Pick any starting vertex; it forms the initial single-node tree.
Step 2
Push its edges to a min-heap
Add all edges from the tree's current vertices to a priority queue keyed by weight.
Step 3
Pop the cheapest edge, extend the tree
If its far endpoint is outside the tree, add the edge and vertex; otherwise discard it (cycle).
Step 4
Repeat until all vertices are included
Continue popping and pushing until the tree spans all V vertices with minimum total weight.
What Interviewer Expects
- Explain the frontier-growing approach vs Kruskal's global edge sort
- State O(E log V) with a binary heap, or O(V^2) on dense/matrix graphs
- Describe how the min-heap picks the next cheapest frontier edge
- Compare when Prim's is preferred over Kruskal's (dense graphs, adjacency matrix)
Common Mistakes
- Forgetting to discard an edge whose far endpoint is already in the tree
- Confusing Prim's with Dijkstra — Prim's minimizes edge weight, Dijkstra minimizes cumulative path distance
- Not knowing the O(V^2) variant exists for dense graphs without a heap
- Starting from multiple disconnected components without noting Prim's requires a connected graph
Best Answer (HR Friendly)
“Prim's algorithm grows a minimum spanning tree from a single starting point, always adding the cheapest edge that connects the tree to a new vertex. I like it for dense graphs because it never needs to sort every edge globally like Kruskal's does — it just keeps expanding the frontier with a priority queue.”
Code Example
import heapq
def prim(vertices, adjacency, start):
visited = {start}
edges = [(weight, start, v) for v, weight in adjacency[start]]
heapq.heapify(edges)
mst = []
while edges and len(visited) < len(vertices):
weight, u, v = heapq.heappop(edges)
if v in visited:
continue
visited.add(v)
mst.append((u, v, weight))
for neighbor, w in adjacency[v]:
if neighbor not in visited:
heapq.heappush(edges, (w, v, neighbor))
return mstFollow-up Questions
- How does Prim's algorithm differ from Dijkstra's algorithm, since both use a min-heap?
- Why is Prim's O(V^2) implementation often preferred for dense graphs?
- How would you modify Prim's algorithm to reconstruct the tree structure, not just total weight?
- What happens if you run Prim's algorithm on a disconnected graph?
MCQ Practice
1. What is Prim's algorithm's time complexity using a binary heap and adjacency list?
With a binary heap, each edge is pushed/popped in O(log V), giving O(E log V) overall.
2. What is the key difference between Prim's algorithm and Dijkstra's algorithm?
Prim's minimizes individual edge weight to grow the tree, while Dijkstra minimizes total path distance from a fixed source.
3. What happens when Prim's algorithm pops an edge whose far endpoint is already in the tree?
An edge to an already-included vertex would create a cycle in the tree, so it is simply discarded.
Flash Cards
How does Prim's algorithm grow the MST? — By always adding the cheapest edge connecting the current tree to a vertex outside it.
What is Prim's time complexity with a binary heap? — O(E log V).
How does Prim's differ from Kruskal's approach? — Prim's grows one connected frontier; Kruskal's sorts all edges globally and adds them if they avoid a cycle.
When is Prim's O(V^2) variant preferred? — On dense graphs represented as an adjacency matrix, where a heap adds unnecessary overhead.