Prim's Algorithm with Priority Queues

In our previous lesson, we established the theoretical foundation for Minimum Spanning Tree (MST) algorithms, focusing on the Cut Property. This property guarantees that the greedy choice of picking the lightest edge across any partition of vertices is always safe. We saw that both Prim's and Kruskal's algorithms are simply different strategies for applying this fundamental principle.

Today, we will transition from theory to practice. Our goal is to implement Prim's algorithm for MST construction using a priority queue. You'll see how this algorithm is structurally very similar to Dijkstra's, which you've already mastered, yet solves a fundamentally different problem. By the end of this lesson, you will be able to write an efficient, interview-ready implementation of Prim's algorithm.

The Algorithm: Growing the MST

Recall the high-level strategy of Prim's algorithm: it grows a single tree, starting from an arbitrary vertex. At each step, it adds the cheapest possible edge that connects a vertex already in the tree to a vertex outside the tree.

A naive way to do this would be to scan all edges crossing the "cut" (the boundary between vertices in the tree and vertices outside) at every step. However, this would be inefficient. A much better approach, and the one we'll focus on, uses a min-priority queue to efficiently find this minimum-weight crossing edge.

The core data structures we'll need are:

1. A Priority Queue (Min-Heap): To store potential edges to add to the MST. We'll store tuples of (weight, vertex), ordered by weight. This allows us to quickly retrieve the cheapest edge to an unvisited vertex.
2. A Visited Array/Set: To keep track of which vertices have already been added to our growing MST. This is crucial for preventing cycles and for handling a key implementation detail.
3. A Parent Array (Optional but good practice): To store the final MST structure if we need to reconstruct the tree itself, not just its total weight.

A Key Implementation Pattern: The "Lazy" Approach

A textbook implementation of Prim's might require a priority queue that supports a decrease-key operation—that is, finding an element in the heap and reducing its priority. However, standard library priority queues (like in C++, Java, or Python's heapq) don't offer this operation efficiently.

Fortunately, there's a simple and elegant workaround that is very common in competitive programming and interviews: the "lazy" approach.

• Instead of updating a key in the priority queue, we simply add a new, updated entry for the same vertex but with a lower-weight edge.
• This means our priority queue might contain multiple entries for the same vertex, representing different paths to it.
• We handle this by using our visited array. When we extract an item (weight, vertex) from the priority queue, we first check if vertex has already been visited.
  • If it has, we simply ignore this entry and continue. It's an outdated, more expensive path to a vertex that's already in our MST.
  • If it hasn't, we process it, add it to the MST, and mark it as visited.

This pattern avoids the need for a complex decrease-key data structure and is a crucial technique to have in your toolkit.

Step-by-Step Execution Walkthrough

To see this process in action, let's watch a detailed walkthrough. The following video from the "take U forward" channel provides an excellent, step-by-step simulation, explaining the role of the priority queue and the visited array.

Implementation in Code

You now have a solid grasp of the algorithm's flow. Let's look at the implementation more closely. A great resource is the GeeksforGeeks article which not only provides clean code in multiple languages but also clearly outlines the steps.

As you can see from the resources, the structure is remarkably similar to Dijkstra's algorithm. The main difference lies in what value is stored and updated:

• Dijkstra's: Stores (distance, vertex), where distance is the cumulative cost from the source node. The relaxation step is dist[v] = dist[u] + weight(u, v).
• Prim's: Stores (weight, vertex), where weight is the cost of a single edge connecting the vertex to the existing tree. The update step is key[v] = weight(u, v).

This distinction is critical. Dijkstra's finds the cheapest path; Prim's finds the cheapest connection.

Application: A LeetCode Problem

Given your experience with LeetCode, it's helpful to see how this classic algorithm appears in modern coding challenges. The problem "Min Cost to Connect All Points" is a direct application of Prim's algorithm. The only twist is that the graph is implicit—you have to generate the edge weights (distances between points) yourself before running the algorithm.

The following video from NeetCode solves this exact problem and provides another excellent walkthrough of Prim's algorithm, this time in Python.

Complexity Analysis

Let's finalize our understanding by analyzing the performance of the priority-queue-based implementation.

• Time Complexity: $O(E\log V)$

  • We add each vertex to the MST exactly once. When we process a vertex, we iterate through its adjacent edges. Over the entire algorithm, we consider each edge at most twice (once from each endpoint).
  • For each of the $O(E)$ edges we consider, we might perform a push operation on the priority queue, which takes $O(\log V)$ time (since the number of items in the PQ is at most $E$, and $\log E$ is $O(\log V)$ for connected graphs).
  • The main loop extracts $V$ vertices from the PQ, each extraction taking $O(\log V)$.
  • Therefore, the dominant factor is $E$ pushes, leading to a total time complexity of $O(E\log V)$.

• Auxiliary Space Complexity: $O(V+E)$

  • We need $O(V+E)$ to store the adjacency list representation of the graph.
  • The visited and parent arrays require $O(V)$ space.
  • In the worst case, the priority queue could hold an entry for every edge, leading to $O(E)$ space.

This is a significant improvement over the naive $O(V^2)$ implementation, especially for sparse graphs where $E$ is much smaller than $V^2$.

Conclusion

In this lesson, you have moved from the theory of MSTs to a practical, efficient implementation of Prim's algorithm.

Key Takeaways:

• Prim's algorithm can be efficiently implemented using a min-priority queue to greedily select the cheapest edge connecting the growing MST to an unvisited vertex.
• The common "lazy" implementation pattern avoids the need for a decrease-key operation by allowing duplicate vertex entries in the priority queue and using a visited check to ignore outdated, more expensive paths.
• The algorithm's structure is very similar to Dijkstra's, but it optimizes for single-edge weights (key[v] = weight(u,v)) rather than cumulative path distances.
• The time complexity with a priority queue is $O(E\log V)$, and the space complexity is $O(V+E)$.

In our next lesson, we will explore the other major MST algorithm, Kruskal's algorithm. You will see how it uses a completely different greedy strategy and relies on the Union-Find data structure you studied earlier to efficiently detect cycles. This will complete your toolkit for solving MST problems.