Kruskal’s Minimum Spanning Tree

Recently, I have been researching image segmentation. I find it fascinating that a machine can, to some degree, mimic the ability of humans to divide a scene into different parts.

Kruskal’s MST (Minimum Spanning Tree) is a second cousin to the image segmentation problem, as it is the foundation for the seminal segmentation algorithm developed by Felzenszwalb and Huttenlocher. Even if you do not know or care about image segmentation, this algorithm serves as a great gateway for anyone looking to get into graph theory, or perhaps algorithms in general.

Graph Theory

Graph theory is weird, but in a cool way. For those aspiring algorithmists who prefer learning visually, this is the topic for you.

In graph theory, graphs refer to data structures consisting of nodes and edges. Edges connect nodes in various ways.

A graph with nodes and edges

And…that is it. No, really. That is it. While there are many different types of graphs, this is the fundamental structure to all graphs. Nodes are connected by edges in different configurations, thus forming different “relationships.”

Minimum Spanning Tree

Let’s say you have a graph; for this example, I will use the following:

This graph has nodes labelled a, b, c, d, e, and f. Think of these nodes as shops in a big mall. The edges, in this case, are different paths you can take to get to each shop.

You may notice that each path is labelled with a number. This number is known as a weight. Generally, the weight is a measure of significance for each edge. If that doesn’t make sense, bear with me.

A minimum spanning tree is a graph which touches all the nodes in the original graph and has the lowest sum of weights. Continuing the mall analogy, we may view the weights as numbers related to the number of steps we take to get to different stores. A lower weight corresponds to a lower step count, and vice versa. Since we are lazy shoppers, we want to reach every store while taking the least steps possible. Thus, we want to minimize the sum of the weights while touching every node.

In this case, the minimum spanning tree would look something like this:

Minimum spanning tree (please excuse the imperfect lines!)

This new graph, highlighted in blue, connects all of the nodes in the graph with the lowest weighted sum: 12. I found this graph by using Kruskal’s algorithm for finding a minimum spanning tree.

Union-Find and Kruskal’s Minimum Spanning Tree

At the heart of Kruskal’s algorithm for finding a minimum spanning tree is the union-find method. This method tries to connect components in a graph without forming a cycle. A cycle is, in essence, nodes in a graph that are connected in a “circular” formation. Here is an example:

A cyclic graph

In this case, if nodes c, d, e, and f were stores, you, the shopper, would be stuck rotating between these four stores for all of eternity. That would not be fun. Removing cycles ensures that the minimum spanning tree contains no extra paths, thus minimizing its weighted sum.

The Union-Find algorithm is easier to explain visually than verbally. If you desire a visual explanation, here is a video which explains Kruskal’s MST algorithm by visualizing Union-Find: Union Find Kruskal’s Algorithm — YouTube.

Union-Find essentially has three steps:

• Sort edges from lowest to highest weight
• Start grouping edges together; this is the union operation
• Check if an edge forms a cycle and ignore it if it does; this is the find operation

In this graph, we have the following edges, sorted in ascending order based on edge weight: c-f, d-e, a-f, c-d, a-b, e-f, b-f, b-c.

Let’s take edge c-f and put it in a new group, G1. Then, let’s put d-e in a new group, G2. The third edge, a-f, is where things get interesting. Both a-f and c-f connect to f, so we may be able to combine them into one group. This is the union operation. However, before we combine edges, we must check if they form a cycle. Here, a-f and c-f do NOT form a cycle, and can thus both be part of G1.

G1 is denoted in blue, G2 in red

Let’s look at the next edge, c-d. Notice how c-d seems to connect G1 and G2. This means that G1, G2, and c-d could become one group. We check if this new group would form a cycle, and it does not. This is the new group, G1:

group G1

We have one last step. Node b has not been touched, so the spanning tree is not complete. However, edge a-b is next on our list. We do a final check to see if adding edge a-b to G1 would form a cycle, and it does not. Therefore, the minimum spanning tree is complete.

Concluding Thoughts

Kruskal’s MST has many applications, such as the segmentation algorithm mentioned before, as well as in mapping software. For example, a mapping app may use Kruskal’s MST to find the quickest routes for visiting a given list of places. As a further step, I would recommend trying to implement this algorithm in code, even if you are not an avid or enthusiastic programmer. The process of breaking any algorithm down into its most logical steps is one of the best ways to understand it.

I hope to cover Felzenszwalb’s and Huttenlocher’s segmentation algorithm in the next article, as it is pertinent to some research that I am doing. As always, if you would like to contact me about anything, please email rmur3211@gmail.com. Thank you for reading, and I hope you learned something new.