# Prim’s Algorithm

Prim’s algorithm generates a minimum spanning tree for a network. Prim’s algorithm has the following steps:

1. Select any vertex. Connect the nearest vertex.
2. Find the vertex that is nearest to the current tree but not already connected and connect that.
3. Repeat step 2 until all vertices are connected.

Often, assuming that you are doing this for the purposes of an exam, you will be told the starting vertex for step 1. If you find that there is more than one vertex equally close in step 2, choose one arbitrarily.

## Example

Finding the minimum spanning tree that follows the road network in southern England.

Using Prim’s algorithm the minimum spanning tree is generated as follows (each selected edge and node is coloured red). Click or tap an image for a larger view.

The solution contains the following edges {(Bristol, Swindon), (Swindon, Oxford), (Oxford, Reading), (Reading, London), (Reading, Southampton)} and the total weight (distance) for the minimum solution is $27 + 30 + 40 + 40 + 42 = 179 \text{(miles)}$.

## Other points to note

Prim’s Algorithm also has a table-based form that can easily be applied to matrices or distance tables. This means that it is particularly suited for applying to a computerised solution.

Due to the number of comparisons of weight needed at each iteration, Prim’s Algorithm is $\text{O}(n^3)$.