本文讲解的例题
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 1135. Connecting Cities With Minimum Cost🔒 | 1135. 最低成本联通所有城市🔒 | 🟠 |
| 1584. Min Cost to Connect All Points | 1584. 连接所有点的最小费用 | 🟠 |
| 261. Graph Valid Tree🔒 | 261. 以图判树🔒 | 🟠 |
最小生成树算法概览 讲解了最小生成树的定义及实际运用场景，没看过的话需要先看下。
最小生成树算法主要有 Prim 算法和 Kruskal 算法两种，这两种算法从原理上讲都是运用贪心思想，但从实现上来说差异还是蛮大的。
本文先来讲比较简单易懂的 Kruskal 算法，然后在下一篇文章中聊 Prim 算法。
Kruskal 算法其实很容易理解和记忆，其关键是要熟悉并查集算法，如果不熟悉，建议先看下前文 Union-Find 并查集算法。
在讲 Kruskal 算法之前，先回顾一下 Union-Find 并查集算法。