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🔒 | 🟠 |
Prerequisite Knowledge
Before reading this article, you should first learn:
In One Sentence
Kruskal's algorithm is a classic way to find the minimum spanning tree in an undirected graph.
It uses a greedy approach: sort the edges first, then use the Union-Find to check for cycles.
Overview of Minimum Spanning Tree Algorithms explains what a minimum spanning tree is and where it is used. If you haven't read it yet, please read it first.
There are two main algorithms for minimum spanning trees: Prim's algorithm and Kruskal's algorithm. Both use greedy ideas, but the ways they work are quite different.
In this article, we will talk about the easier Kruskal's algorithm. In the next article, we will cover Prim's algorithm.
Kruskal's algorithm is simple to understand and remember. The key is to know the Union-Find algorithm well. If you are not familiar with it, read Union-Find Algorithm first.
Before we start with Kruskal's algorithm, let's quickly review the Union-Find data structure.