Eric Christopher Seidel 


Prim's Algorithm 

The DemonstrationOk. 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. The ProofClaim: 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 n1 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 {e_{1}, e_{2}, …, e_{n1}} where e_{k} for 1 Ó kÓ n1 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 {v_{1}, v_{2}, …, v_{n}}, where edge e_{k} connects vertices v_{k} and v_{k+1}. Let e_{i} be the first edge of T that does not also belong to H. Let U={v_{1}, v_{2}, …, v_{i} }. If v(T) is the set of all vertices in T, then v(T)U={v_{i+1}, v_{i+2}, …, v_{n}}. H is a tree, so the addition of edge e_{i} to H forms a unique cycle. e_{i} connects v_{i} and v_{i+1} and therefore the sets of vertices U and v(T)U. However, because e_{i} is part of a cycle in H, H also contains some other edge e_{0} which connects U and v(T)U. We now form a new spanning tree H’ by deleting e_{0} from H and adding e_{i}. H’ will indeed be a spanning tree because it will be connected (removing e_{0} disconnects U and v(T)U and adding e_{i} reconnects them) and acyclic (the cycle formed by adding e_{i }is destroyed by removing e_{0}). w(H’) = w(H) + w(e_{i}) — w(e_{0}). e_{i} and e_{0} are both frontier edges for the set U, so w(e_{i}) Ó w(e_{0}) (because Prim’s algorithm chose e_{i} over e_{0}). 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. 


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