Prim’s Algorithm

The crux of it

The idea is to build a subgraph $K$ of $G=(V,E)$ by adding an edge to it in every round such that $K$ remains a tree after each round.

Conceptually, in every round, the vertices of $G$ are regrouped as:

1. Those in $K$
2. Those in $K^C$, the complement of $K$

We refer to an edge as a boundary-edge if it has one end-vertex in $K$ and the other in $K^C$. For the example shown below, we show the boundary-edges as dotted, and the edges in $K$ are highlighted in red. Note how the edges in $K$ form a tree.

Here is how the algorithm works:

1. An arbitrary vertex $r$ of $G$ is chosen as the root and placed in $K$.
2. At each subsequent step, we pick a boundary-edge of the smallest weight and add it to $K$. Adding an edge to $K$ entails also adding its other end-vertex to $K$.

This algorithm ensures that $K$ remains a tree after every round. Here is why:

1. It remains connected after each round.

2. It remains acyclic after each round.

Conclusion: Since, in each round, a new vertex becomes part of the tree $K$, by the end of the execution, $K$ contains all vertices of the original graph and is, therefore, a spanning tree.

In fact, $K$ is guaranteed to be a minimum spanning tree, but we defer showing this for now.

A dry run

Implementation details

Let’s drill down and see how to implement Prim’s algorithm.

Priority queue

Since in each round, we want to pick a minimum-weight boundary-edge, we could use a priority queue for the boundary-edges. However, each boundary-edge has exactly one end-vertex in $K^C$. So, instead, we make the simpler decision to use the priority queue to keep the vertices in $K^C$, such that each vertex $v$ has an attribute $v.cost$ to store the weight of a minimum-weight boundary-edge incident on $v$.

Note: The attribute $v.cost$ also serves as the priority key of $v$. If a vertex is extracted from the priority queue, it implies that the vertex has an incident boundary-edge of the smallest weight over all the boundary-edges incident on vertices in $K^C$.

Vertices that are not in the priority queue are exactly the vertices in $K$.

Implementing the tree

Instead of maintaining an explicit data structure for the tree $K$ ...