Course contentsShow
← Computer Science
Lesson 1018 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Prim's Algorithm: Priority Queue Implementation

Implement Prim's algorithm using a min-heap priority queue to efficiently select the next edge to add.

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

  1. Initialize: Pick any starting node, mark it as visited, and push all its edges into the min-heap.
  2. Extract minimum: Pop the lightest edge from the heap.
  3. Check validity: If the edge leads to an already-visited node, discard it (it would create a cycle). Otherwise, add it to your MST.
  4. Expand: Mark the new node as visited and push all its edges into the heap.
  5. 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.