Prim's Algorithm: Priority Queue Implementation
You'll learn how to implement Prim's algorithm efficiently using a min-heap to quickly find the cheapest edge at each step.
The Core Idea
In the previous lesson, you saw Prim's algorithm conceptually: start with any node, then repeatedly add the cheapest edge connecting your growing tree to a new node. But how do we quickly find that "cheapest edge" each time?
The answer: use a min-heap priority queue. Instead of scanning all edges manually (which is slow), we store candidate edges in a min-heap, organized by weight. The heap automatically keeps the lightest edge at the top, so we can extract it in O(log E) time.
How It Works
- Initialize: Pick any starting node, mark it as visited, and push all its edges into the min-heap.
- Extract minimum: Pop the lightest edge from the heap.
- Check validity: If the edge leads to an already-visited node, discard it (it would create a cycle). Otherwise, add it to your MST.
- Expand: Mark the new node as visited and push all its edges into the heap.
- Repeat until the heap is empty or you've visited all nodes.
Think of it like building a snowball: you always pick up the closest bit of snow (lightest edge) that expands your snowball without overlapping what you already have.
Why Priority Queue?
Without a heap, you'd scan all edges from your tree every iteration—potentially O(V) operations per step, giving O(V²) overall. With a binary heap, extracting the minimum and inserting edges costs O(log E), resulting in O(E log V) total time, much faster for sparse graphs.
Key Takeaway: Implementing Prim's with a min-heap priority queue reduces time complexity from O(V²) to O(E log V) by efficiently maintaining and extracting the lightest frontier edge at each step.