## Kruskal’s Algorithm

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

Kruskal’s algorithm has the following steps:

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

Using Kruskal’s algorithm the minimum spanning tree is generated as follows (each selected edge is coloured red).

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