Kruskal’s Algorithm

Kruskal’s algorithm finds the minimum spanning tree for a network.

Kruskal’s algorithm has the following steps:

  1. Select the edge with the lowest weight that does not create a cycle. If there are two or more edges with the same weight choose one arbitrarily.
  2. Repeat step 1 until the graph is connected and a tree has been formed.

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 Kruskal’s algorithm the minimum spanning tree is generated as follows (each selected edge is coloured red).

Figure 2: Kruskal solution step 1 Figure 3: Kruskal solution step 2 Figure 4: Kruskal solution step 3
Figure 5: Kruskal solution step 4 Figure 6: Kruskal solution step 5 Figure 7: Kruskal 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).