# Prim's algorithm

*1,014*pages on

this wiki

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.

## Algorithm

Let be a connected undirected graph, let be a bijection from its edges to their weights and let be a graph that will form a minimal spanning tree of , where and are initially empty.

### Initial Stage

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

### Iterative Stage

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