Prim’s Algorithm – table form

Prim’s algorithm is also suitable for use on distance tables or matrices, 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.

We will look again 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: Network of road connections in southern England.

The network shown in Figure 1 can be represented by the adjacency matrix shown in Table 1.

Bristol
London
Oxford
Reading
Southampton
Swindon
Bristol×××7540
London×6040×70
Oxford×6027×30
Reading×40274245
Southampton75××4270
Swindon4070304570
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×××7540
London×6040×70
Oxford×6027×30
Reading×40274245
Southampton75××4270
Swindon4070304570
Table 2: Prim’s algorithm first iteration.

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×××7540
London×6040×70
Oxford×6027×30
Reading×40274245
Southampton75××4270
Swindon4070304570
Table 3: Prim’s algorithm second iteration.

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×××7540
London×6040×70
Oxford×6027×30
Reading×40274245
Southampton75××4270
Swindon4070304570
Table 4: Prim’s algorithm third iteration.

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×××7540
London×6040×70
Oxford×6027×30
Reading×40274245
Southampton75××4270
Swindon4070304570
Table 5: Prim’s algorithm fourth iteration.

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×××7540
London×6040×70
Oxford×6027×30
Reading×40274245
Southampton75××4270
Swindon4070304570
Table 6: Prim’s algorithm fifth and final iteration.

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.

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.