next up previous contents index Search
Next: 0.4.5.1.1 Source Code Up: 0.4.5 Spanning Trees Previous: 0.4.5 Spanning Trees

       
0.4.5.1 Prim's Algorithm

This algorithm for finding a minimal cost spanning tree in a connected graph is very easy to follow. It begins by adding the lowest cost edge and its two endpoints to the solution set. It then loops adding the lowest cost edge that connects a vertex in the solution set to one outside it. It also adds the endpoint of this edge that is not already in the solution set. The algorithm terminates when all vertices are in the solution set. The edges and vertices in the solution set at this point constitute a minimal cost spanning tree of the input graph.



 
Scott Gasch
1999-07-09