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.

Finding the minimum spanning tree that follows the road network in southern England:
Figure 1: Roads connecting towns 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).

Figure 2: Prim's solution step 1 Figure 3: Prim's solution step 2 Figure 4: Prim's solution step 3
Figure 5: Prim's solution step 4 Figure 6: Prim's solution step 5 Figure 7: Prim's solution step 6

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