next up previous contents index CD CD Algorithms
Next: Kruskal's Algorithm Up: Minimum Spanning Trees Previous: Minimum Spanning Trees

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 tex2html_wrap_inline25280  


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 tex2html_wrap_inline25282 .

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), tex2html_wrap_inline25286 consisted of a set of edges that was a subtree of a minimum spanning tree tex2html_wrap_inline25288 , 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 tex2html_wrap_inline25292 , using an edge tex2html_wrap_inline25294 , where tex2html_wrap_inline25296 is in tex2html_wrap_inline25298 but tex2html_wrap_inline25300 is not. This edge tex2html_wrap_inline25302 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 tex2html_wrap_inline25310 from tex2html_wrap_inline25312 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, tex2html_wrap_inline25318 , implementation by avoiding the need to sweep through more than n edges in any iteration.

next up previous contents index CD CD Algorithms
Next: Kruskal's Algorithm Up: Minimum Spanning Trees Previous: Minimum Spanning Trees

Mon Jun 2 23:33:50 EDT 1997