Prim’s Algorithm – Table Form

Prim’s algorithm is also suitable for use on distance tables, or the equivalent for the problem. This is useful for large problems where drawing the network diagram would be hard or time-consuming.

That tables can be used makes the algorithm more suitable for automation than Kruskal’s algorithm. The reason for this is that the data used would have to be sorted to be used with Kruskal’s algorithm. With Prim’s algorithm, however, it is only the minimum value that is of interest, so no sorting is normally necessary.

Looking at our question that requires a minimum spanning tree for the network of towns in the south of England using main road connections. The network diagram is as shown in figure 1.

Figure 1: Roads connecting towns in southern England

Figure 1: Roads connecting towns in southern England

Bristol London Oxford Reading Southampton Swindon
Bristol × × × 75 40
London × 60 40 × ×
Oxford × 60 27 × 30
Reading × 40 27 42 45
Southampton 75 × × 42 70
Swindon 40 × 30 45 70

Table 1: tabular version of road network. × means no direct link.

The tabular form of Prim’s algorithms has the following steps:

  1. Select any vertex (town). Cross out its row. Select the shortest distance (lowest value) from the column(s) for the crossed out row(s). Highlight that value.
  2. Cross out the row with the newly highlighted value in. Repeat step 1. Continue until all rows are crossed out.
  3. Once all rows are crossed out, read off the connections. The column and the row of each highlighted value are the vertices that are linked and should be included.

Example

First we will choose a town at random – Swindon – and cross out that row. Then we highlight the smallest value in the column for the crossed out row.

Bristol London Oxford Reading Southampton Swindon
Bristol × × × 75 40
London × 60 40 × ×
Oxford × 60 27 × 30
Reading × 40 27 42 45
Southampton 75 × × 42 70
Swindon 40 × 30 45 70

Next we need to cross out the row with the newly-highlighted value in (the Oxford row). Then we look for, and highlight, the smallest value in the columns for the two crossed out rows (Swindon and Oxford).

Bristol London Oxford Reading Southampton Swindon
Bristol × × × 75 40
London × 60 40 × ×
Oxford × 60 27 × 30
Reading × 40 27 42 45
Southampton 75 × × 42 70
Swindon 40 × 30 45 70

Next we need to cross out the row with the newly-highlighted value in (the Reading row). Then we look for, and highlight, the smallest value in the columns for the three crossed out rows (Swindon, Oxford, and Reading).

Bristol London Oxford Reading Southampton Swindon
Bristol × × × 75 40
London × 60 40 × ×
Oxford × 60 27 × 30
Reading × 40 27 42 45
Southampton 75 × × 42 70
Swindon 40 × 30 45 70

Next we need to cross out the row with the newly-highlighted value in (the Bristol row). Then we look for, and highlight, the smallest value in the columns for the four crossed out rows (Swindon, Oxford, Reading, and Bristol).

Bristol London Oxford Reading Southampton Swindon
Bristol × × × 75 40
London × 60 40 × ×
Oxford × 60 27 × 30
Reading × 40 27 42 45
Southampton 75 × × 42 70
Swindon 40 × 30 45 70

Next we need to cross out the row with the newly-highlighted value in (the London row). Then we look for, and highlight, the smallest value in the columns for the crossed out rows (Swindon, Oxford, Reading, Bristol, and Southampton).

Bristol London Oxford Reading Southampton Swindon
Bristol × × × 75 40
London × 60 40 × ×
Oxford × 60 27 × 30
Reading × 40 27 42 45
Southampton 75 × × 42 70
Swindon 40 × 30 45 70

We’ve now selected a value from the last undeleted row. This means we’ve selected all the edges that we need to create the minimum spanning tree for the network. All we have left to do is write out the connections between the vertices.

The connections in the network are found by taking the row and column headings for each selected value in the table. The edges are: {(Bristol, Swindon), (London, Reading), (Oxford, Swindon), (Reading, Oxford), (Southampton, Reading)}. This is the set of edges as in the minimum spanning tree generated by the diagrammatic version of the algorithm.