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.

Figure 1: simplified road network of southern England, Swindon selected as a start point.
Figure 2: Prim’s algorithm step 1, connecting Swindon to Oxford, the nearest adjacent node.
Figure 3: Prim’s algorithm step 2, connecting Oxford to Reading, the nearest node not already in the tree.
Figure 4: Prim’s algorithm step 2, connecting Swindon to Bristol, the nearest node not already in the tree. Bristol was chosen arbitrarily at this point, but London is the same distance and could have equally have been chosen.

Figure 5: Prim’s algorithm step 2, connecting Reading to London, the nearest node not already in the tree.

Figure 6: Prim’s algorithm step 2, connecting Reading to Southampton, the nearest node not already in the tree.

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