Prim's algorithm
From Mathematics
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.
Contents |
[edit] 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.
[edit] 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 .
[edit] 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.
