📚 精选阅读
- LeetCode 1584 - 连接所有点的最小费用
-
难度：中等 MST 基础应用 - 链接：https://leetcode.cn/problems/min-cost-to-connect-all-points/
-
- LeetCode 1167 - 连接棒料棒的最小成本
-
难度：中等 哈夫曼变形 - 链接：https://leetcode.cn/problems/minimum-cost-to-connect-sticks/
-
- LeetCode 1135 - 连接城市的最低成本
-
难度：简单 Kruskal 直接应用 - 链接：https://leetcode.cn/problems/minimum-cost-to-connect-cities/
-
- 《MST 算法详解》 — 经典图论
- 图解 Prim 和 Kruskal 算法
- 推荐：OI Wiki / 洛谷博客
- 《次小生成树》 — 竞赛内容
- 枚举 + LCA / 瓶颈路
- 进阶学习
🔧 实战路径
第一阶段：Kruskal 入门
├─ LeetCode 1135：套模板
├─ 理解并查集的路径压缩和按秩合并
└─ 为什么用并查集（检测环）
第二阶段：Prim 进阶
├─ 用堆实现 Prim
├─ 对比 Kruskal 和 Prim 的适用场景
└─ 什么时候用哪个？
第三阶段：变形题
├─ LeetCode 1584：曼哈顿距离建图
├─ LeetCode 1167：哈夫曼思想
└─ 理解 MST 的变形本质
📖 推荐学习顺序
1. 理解 MST 的定义 → 什么是生成树
2. 理解切分定理 → 为什么 Kruskal/Prim 正确
3. 画图模拟 Kruskal → 选边、不成环
4. 画图模拟 Prim → 从点扩展
5. 理解并查集 → 检测环
6. 刷 LeetCode 1584 → 综合应用
💡 面试常考点
| 考点 | 对应题目 | 难度 |
|---|---|---|
| Kruskal 模板 | 1135 | 简单 |
| Prim 模板 | 1584 变形 | 中等 |
| 并查集 | 1135、1584 | 中等 |
| 哈夫曼变形 | 1167 | 中等 |
| 次小生成树 | 竞赛题 | 困难 |
面试高频问题：
- Kruskal 和 Prim 的区别？各自适合什么图？
- 为什么 Kruskal 用并查集检测环？
- 切分定理是什么？证明 MST 的正确性。