prim

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×60–27×30
Reading×4027–4245
Southampton75××42–70
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×60–27×30
Reading×4027–4245
Southampton75××42–70
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×60–27×30
Reading×4027–4245
Southampton75××42–70
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×60–27×30
Reading×4027–4245
Southampton75××42–70
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×60–27×30
Reading×4027–4245
Southampton75××42–70
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×60–27×30
Reading×4027–4245
Southampton75××42–70
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.

Prim’s Complexity

Prim’s algorithm starts by selecting the least weight edge from one node. In a complete network there are (n - 1) edges from each node.

At step 1 this means that there are (n - 1) - 1 comparisons to make.

Having made the first comparison and selection there are (n - 2) unconnected nodes, with a edges joining from each of the two nodes already selected. This means that there are (n - 2) - 1 comparisons that need to be made.

Carrying on this argument results in the following expression for the number of comparisons that need to be made to complete the minimum spanning tree: ((n - 1) - 1) + (2(n - 2) - 1) + (3(n - 3) - 1) + \dotsc + ((n - 1)(n - (n - 1)) - 1)

The result is that Prim’s algorithm has cubic complexity.