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