Eric Christopher Seidel








Academic Work



Prim's Algorithm

The Demonstration

Ok. Here is the java applet version of Prim's algorithm. It draws both graphs, and then when you click start, it applies the algoritm and outputs the second graph. It also outputs some debugging info to "standard out" which under most browsers is the "java messages" window. It is by no means done, but it is a start.
You can grab the C++ source code for this algoritm, or the Java 1.18 source code.
The applet should appear in a seperate window. Closing this window will also close the applet window.

Your browser does not support Java, so nothing is displayed.

The Proof

Claim: Prim’s algorithm produces a minimum spanning tree.

Proof: Let G be a connected, weighted graph with n vertices. Let T be the subgraph produced by Prim’s algorithm. We know T is acyclic because in the process of creating T, we only add an edge if it has one end not already in T. Furthermore, we know that T is connected and contains all the vertices of G because the algorithm terminates only when all vertices in G are connected to the starting vertex of the algorithm. Thus, T is a spanning tree. Hence, we know that T has n vertices and n-1 edges.

We need to show that T is a minimum spanning tree. Assume T is not a minimum spanning tree. Then there must be at least one other tree which is a minimum spanning tree. Let H be the minimum spanning tree having the highest number of edges in common with T.

Label the edges of T {e1, e2, …, en-1} where ek for 1 k n-1 is the kth edge added to T in Prim’s algorithm. The weight of T, w(T), is the sum of the weights of the individual edges. Label the vertices of T {v1, v2, …, vn}, where edge ek connects vertices vk and vk+1.

Let ei be the first edge of T that does not also belong to H. Let U={v1, v2, …, vi }. If v(T) is the set of all vertices in T, then v(T)-U={vi+1, vi+2, …, vn}.

H is a tree, so the addition of edge ei to H forms a unique cycle. ei connects vi and vi+1 and therefore the sets of vertices U and v(T)-U. However, because ei is part of a cycle in H, H also contains some other edge e0 which connects U and v(T)-U.

We now form a new spanning tree H’ by deleting e0 from H and adding ei. H’ will indeed be a spanning tree because it will be connected (removing e0 disconnects U and v(T)-U and adding ei reconnects them) and acyclic (the cycle formed by adding ei is destroyed by removing e0).

w(H’) = w(H) + w(ei) — w(e0). ei and e0 are both frontier edges for the set U, so w(ei) w(e0) (because Prim’s algorithm chose ei over e0). Thus, w(H’) w(H). But H is a minimum spanning tree, so w(H’) = w(H). However, H’ has more edges in common with T than H does, which is a contradiction to our definition of H.

Thus, T is a minimum spanning tree.

since 2/02

Last updated: Saturday, June 29, 2002 0:52 AM