Kruskal Minimum Spanning Tree Algorithm
Note
Now all the plugins has supported English. I'm still improving the website...
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 1135. Connecting Cities With Minimum Cost🔒 | 🟠 |
| 1584. Min Cost to Connect All Points | 🟠 |
| 261. Graph Valid Tree🔒 | 🟠 |
Prerequisites
Before reading this article, you should first learn:
Among the well-known algorithms in graph theory are Dijkstra's Shortest Path Algorithm, Cycle Detection and Topological Sorting, Bipartite Graph Detection Algorithm, and today's topic: the Minimum Spanning Tree (MST) algorithms.
The two main MST algorithms are Prim's Algorithm and Kruskal's Algorithm. Although both use the greedy approach, they differ significantly in their implementations.
In this article, we will first discuss the simpler and more understandable Kruskal's Algorithm. In the next article, Prim's Algorithm Template, we will cover Prim's Algorithm.
Kruskal's Algorithm is actually quite easy to understand and remember. The key is to be familiar with the Union-Find algorithm. If you're not familiar with it yet, I recommend reading our previous article on the Union-Find Algorithm.
Now, let's start with the definition of a Minimum Spanning Tree.
What is a Minimum Spanning Tree
First, the fundamental difference between a "tree" and a "graph": A tree does not contain cycles, while a graph can contain cycles.
If a graph has no cycles, it can be stretched into the shape of a tree. To put it technically, a tree is an "acyclic connected graph."
So, what is a "spanning tree" of a graph? Literally, it is a tree that includes all the nodes of the graph. Technically speaking, a spanning tree is an "acyclic connected subgraph" that contains all the vertices of the graph.
It's easy to see that a graph can have many different spanning trees. For example, the red edges in the graph below form two different spanning trees:
In a weighted graph, each edge has a weight, so each spanning tree has a total weight. For example, in the graph above, the total weight of the spanning tree on the right is obviously less than that of the spanning tree on the left.
Therefore, the minimum spanning tree is easy to understand: among all possible spanning trees, the one with the smallest total weight is called the "minimum spanning tree".
Tips
Generally speaking, we calculate the minimum spanning tree in an undirected weighted graph, so in real-world scenarios where minimum spanning tree algorithms are used, the edge weights of the graph usually represent costs or distances.
Before discussing the Kruskal algorithm, we need to review the Union-Find data structure.