## Prim’s Algorithm

Prim’s algorithm generates a minimum spanning tree for a network.

Prim’s algorithm has the following steps:

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

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

Figure 1: Roads connecting towns in southern England

Using Prim’s algorithm the minimum spanning tree is generated as follows (each selected edge is coloured red).

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 (miles).