The minimum spanning tree problem: Kruskal's algorithm

In the previous activity, we looked at the GigaFibre scenario where we were trying to find a way to connect a set of cities in the cheapest way possible. This is a really important problem for network providers, such as telephone network companies and utility companies.

This problem is called the minimum spanning tree problem. The minimum spanning tree problem asks if we are given a graph with numbers associated with each of the edges, can we find a tree where the sum of the edges has the smallest value possible?

Solving the minimum spanning tree problem

Joseph Kruskal was a notable graph theorist and mathematician. His early research focused on topology and algebraic geometry (two topics in mathematics), but he later became interested in graph theory. He is perhaps best known for developing Kruskal algorithm, which is a popular algorithm used for finding minimum spanning trees in graphs.

An algorithm is like a recipe for cooking; it is a set of steps that given some input will produce an output.

Kruskal invented an set of steps that can produce a solution to the minimum spanning tree problem for any graph with numbers associated with the edges. Let’s take a look.

Kruskal’s algorithm

In the video above, Sam explains how Kruskal’s algorithm works.

1. Take the edges of the graph and write them in a list, ordering them by the edge number from lowest to highest. The lowest number should be at the top of the list an the highest number at the bottom of the list.
2. Starting from the top of the list, add the edge with the lowest number to the spanning tree, if by adding the edge it does not introduce a cycle into the graph. Remove the edge from the list.
3. Repeat step 2 until you have removed all of the edges off of your list. In the next step, you will see a video explaining how Kruskal’s algorithm works.