kruskal

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

Kruskal’s Complexity

In Kruskal’s algorithm we need to find edge with the lowest weight at each step. Taking the worst case of a complete network there will be _nC^2 edges, which is equal to \frac{1}{2}[n(n + 1)] possible edges. Inspecting each edge to determine the one with the lowest weight is the most time consuming job so the number of inspections to complete the problem will give an indication of the complexity of the algorithm.

In the first round of inspections, all of the edges need to be inspected and compared. There will be \frac{1}{2}[n(n + 1)] - 1 comparisons to make.

In the second round of inspections, all of the edges, except the one already selected, need to be inspected and compared. There will be \frac{1}{2}[n(n + 1)] - 2 comparisons to make.

In a spanning tree for a network with n nodes, there will be (n - 1) edges that will have to be selected. This would require the following number of comparisons to be made in total:
{\frac{1}{2}[n(n + 1)] - 1} + {\frac{1}{2}[n(n + 1)] - 2} + {\frac{1}{2}[n(n + 1)] - 3} + \dotsc + {\frac{1}{2}[n(n + 1)] - (n - 1)}

After messing about with all of the algebra you discover that this can also be written as: \frac{1}{2}n(n - 1)(n - 2) = \frac{1}{2}(n^3 - 3n^2 + 2n). It follows that Kruskal’s algorithm has cubic complexity.