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.

Mon Jun 2 23:33:50 EDT 1997