Kruskal Minimum Spanning Tree Algorithm
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, let's clarify the fundamental difference between a "tree" and a "graph": a tree does not contain cycles, while a graph can.
If a graph has no cycles, it can be stretched into the shape of a tree. To put it professionally, a tree is an "acyclic connected graph."
So, what is a "spanning tree" of a graph? As the name suggests, it is a tree that includes all the nodes of the graph. More formally, a spanning tree is an "acyclic connected subgraph" that contains all the vertices of the graph.
It's easy to imagine that a graph can have many different spanning trees. For example, in the graph below, the red edges form two different spanning trees:
For a weighted graph, each edge has a weight, so each spanning tree has a total weight. In the above graph, the total weight of the right spanning tree is clearly smaller than that of the left spanning tree.
Thus, the concept of a minimum spanning tree is straightforward: among all possible spanning trees, the one with the smallest total weight is called the "minimum spanning tree."
Tip
Generally, we calculate the minimum spanning tree in an undirected weighted graph. In real-world scenarios where minimum spanning tree algorithms are used, the edge weights typically represent scalars like cost or distance.
Before discussing the Kruskal algorithm, we need to review the Union-Find disjoint-set algorithm.