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.

Example

Finding the minimum spanning tree that follows the road network in southern England

Using Kruskal’s algorithm the minimum spanning tree is generated as follows (each selected edge is coloured red). Click or tap an image for a larger view.

Figure 1: Roads connecting towns in southern England
Figure 1: Roads connecting towns in southern England
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

The solution for the minimum spanning tree contains the edges {(Bristol, Swindon), (Swindon, Oxford), (Oxford, Reading), (Reading, London), (Reading, Southampton)}. The total weight (distance) for the minimum solution is 27 + 30 + 40 + 40 + 42 = 179 \text{(miles)}.

Leave a Reply

Your email address will not be published. Required fields are marked *

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