Correctness Proof for Prim’s Algorithm

Why Prim’s Algorithm Works

The proof of correctness for Prim’s minimum spanning tree (MST) algorithm holds a special place in my heart, because it was what turned me into a computer scientist. Prim’s algorithm is what we call a “greedy algorithm,” meaning it follows what seems like a good strategy to produce a good result. But “seems like” isn’t enough – does it produce an optimal solution? Always? Sometimes greedy strategies work, and sometimes they don’t, and so the most important part is whether you can prove that the solution you get is always optimal. When I first saw that proof of correctness it was a revelation, like getting a glimpse into a deep and important truth. This hooked me on computer science for good!

I first wrote the proof below when I taught data structures in Fall 2016 at UNC Greensboro. The prerequisite for data structures was discrete mathematics (called “Foundations of Computer Science” in the UNCG program), which used the textbook by James L. Hein, and so this proof used the presentation of the algorithm from that book. The pseudocode below is sightly modified from Hein’s presentation.

The intuition behind Prim’s algorithm is simple. We “grow” a tree S from some start vertex (selected in line 2 below), where each step connects a new vertex to S. We keep track of the vertices in S with the set W (initialized on line 3 and updated on line 8), and since new vertices are added to S by connecting to the existing tree, S is always connected. Therefore, when W=V and the algorithm terminates, S must be a spanning tree. Is it a minimum spanning tree? That’s what we prove in the theorem below.

\begin{algorithm} \caption{Prim's Algorithm for computing minimum spanning trees} \begin{algorithmic} \Procedure{Prims}{$G=(V,E)$} \State Pick any $v\in V$ \State $W= \{v\}$ \State $S= \emptyset$ \While {$W\neq V$} \State $\{x,y\}=$ min weight edge with $x\in W$ and $y\in V-W$ \State $S= S\cup\{\{x,y\}\}$ \State $W= W\cup \{y\}$ \EndWhile \Return $S$ \EndProcedure \end{algorithmic} \end{algorithm}

There are multiple ways of proving that Prim’s algorithm always produces a minimum spanning tree. The proof below is fairly direct, and has the benefit that the same proof structure can be used to prove that Dijkstra’s algorithm computes shortest paths. A significantly different proof is in the Introduction to Algorithms book by Cormen, Leiserson, Rivest, and Stein, and while I like that proof quite a bit since it gives additional insight into minimum spanning trees, it requires building up additional terminology and properties specific to minimum spanning trees, and doesn’t generalize to problems in different domains, like Dijkstra’s algorithm (it does however, make correctness proofs for other minimum spanning tree algorithms, like Kruskal’s algorithm, easier).

Theorem 1

If S is the spanning tree selected by Prim’s algorithm for input graph G=(V,E), then S is a minimum-weight spanning tree for G.

NoteProof

The proof is by contradiction, so assume that S is not minimum weight. Let ES=(e_1,e_2,\cdots,e_{n-1}) be the sequence of edges chosen (in this order) by Prim’s algorithm, and let U be a minimum-weight spanning tree that contains edges from the longest possible prefix of sequence ES.

Let e_i=\{x,y\} be the first edge added to S by Prim’s algorithm that is not in U, and let W be the set of vertices immediately before \{x,y\} is selected. Notice that it follows that U contains edges e_1,e_2,\cdots,e_{i-1} but not edge e_i.

There must be a path x\leadsto y in U, since it is a spanning tree, so let \{a,b\} be the first edge on this path with one endpoint (a) inside W, and the other endpoint (b) outside W, as in the following picture:

Figure 1: Illustrating relation between U and the state of Prim’s algorithm when \{x,y\} is selected

Define the set of edges T=U\cup\{\{x,y\}\}-\{\{a,b\}\} (in other words, we take out \{a,b\} and put in \{x,y\} instead), and notice that T is a spanning tree for graph G. Consider the three possible cases for the weights of edges \{x,y\} and \{a,b\}:

• Case 1, w(\{x,y\})<w(\{a,b\}): In this case, in creating T we have added an edge that has smaller weight then the one we removed, and so w(T)<w(U). However, this is impossible, since U is a minimum-weight spanning tree.

• Case 2, w(\{x,y\})=w(\{a,b\}): In this case w(T)=w(U), so T is also a minimum spanning tree. Furthermore, since Prim’s algorithm hasn’t selected edge \{a,b\} yet, that edge cannot be one of e_1,e_2,\cdots,e_{i-1}. This implies that T contains edges e_1,e_2,\cdots,e_i, which is a longer prefix of ES than U contains. This contradicts the definition of tree U.

• Case 3, w(\{x,y\})>w(\{a,b\}): In this case, since the weight of edge \{a,b\} is smaller, Prim’s algorithm will select \{a,b\} at this step. This contradicts the definition of edge e_i=\{x,y\}.

Since all possible cases lead to contradictions, our original assumption (that S is not minimum-weight) must be invalid. This completes the proof.