Prim's algorithm is a common method for finding a minimal spanning tree of a connected, weighted, undirected graph. It is a greedy algorithm and, surprisingly, is always correct despite its simplicity. It is not hard at all to execute this algorithm with pencil and paper. However, its proof is a little more involved.
- Select an edge such that minimizes . If there is more than one choice, pick out any one arbitrarily. Add to and add its endpoints to .
- Select an edge adjacent to such that minimizes . As before, if there is more than one edge that minimizes weight, the choice is arbitrary. Add to and add the endpoint of that is not currently in to .
- Repeat previous step until , i.e. until the minimal spanning tree has one less edge than the number of vertices. This step indicates the algorithm is complete, since a tree with vertices necessarily has edges.