Prim's Algorithm

 

Every vertex will appear in the minimum spanning tree of any connected graph G. Prim's minimum spanning tree algorithm starts from one vertex and grows the rest of the tree one edge at a time.

In greedy algorithms, we make the decision of what to do next by selecting the best local option from all available choices without regard to the global structure. Since we seek the tree of minimum weight, the natural greedy algorithm for minimum spanning tree repeatedly selects the smallest weight edge that will enlarge the tree.  

 
Figure: Where Prim's algorithm goes bad? No, because  

Prim-MST(G)

		Select an arbitrary vertex  to start the tree from.

		While (there are still non-tree vertices)

				 Select the edge of minimum weight between a tree and non-tree vertex

				 Add the selected edge and vertex to the tree   .

Prim's algorithm clearly creates a spanning tree, because no cycle can be introduced by adding edges between tree and non-tree vertices. However, why should it be of minimum weight over all spanning trees? We have seen ample evidence of other natural greedy heuristics that do not yield a global optimium. Therefore, we must be particularly careful to demonstrate any such claim.

Suppose that there existed a graph G for which Prim's algorithm did not return a minimum spanning tree. Since we are building the tree incrementally, this means that there must have been some particular instant where we went wrong. Before we inserted edge (x,y), consisted of a set of edges that was a subtree of a minimum spanning tree , but choosing edge (x,y) took us away from a minimum spanning tree. But how could it? There must be a path p from x to y in , using an edge , where is in but is not. This edge must have weight at least that of (x,y), or else Prim's algorithm would have selected it instead of (x,y) when it had the chance. Inserting (x,y) and deleting from leaves a spanning tree no larger than before, meaning that Prim's algorithm could not have made a fatal mistake in selecting edge (x,y). Therefore, by contradiction, Prim's algorithm has to construct a minimum spanning tree.

Prim's algorithm is correct, but how efficient is it? That depends on which data structures are used to implement it, but it should be clear that O(nm) time suffices. In each of n iterations, we will scan through all the m edges and test whether the current edge joins a tree with a non-tree vertex and whether this is the smallest edge seen thus far. By maintaining a Boolean flag along with each vertex to denote whether it is in the tree or not, this test can be performed in constant time. In fact, better data structures lead to a faster, , implementation by avoiding the need to sweep through more than n edges in any iteration.