Kruskal 最小生成树算法
原创约 4958 字
本文讲解的例题
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 并查集算法。