题目描述
思路解析动画文字版
记住这一句，下面每条边都在套它。
起手：5 个点各自孤立，一条边都还没选（费用 0）。下面把「所有点对」按曼哈顿距离从小到大排好，逐条尝试连接。
看边 P1-P3：曼哈顿距离 = |2-5| + |2-2| = 3。这是当前最短的可用边，查两端的根——
根不同、不成环 → 选入这条边！两组并成一组（同色），累计费用 +3 = 3。已选 1/4 条。
看边 P0-P1：曼哈顿距离 = |0-2| + |0-2| = 4。这是当前最短的可用边，查两端的根——
根不同、不成环 → 选入这条边！两组并成一组（同色），累计费用 +4 = 7。已选 2/4 条。
看边 P3-P4：曼哈顿距离 = |5-7| + |2-0| = 4。这是当前最短的可用边，查两端的根——
根不同、不成环 → 选入这条边！两组并成一组（同色），累计费用 +4 = 11。已选 3/4 条。
看边 P0-P3：曼哈顿距离 = |0-5| + |0-2| = 7。先查根——
P0、P3 已经在同一组里，再连会成环 → 跳过这条边，费用不变（仍是 11）。
看边 P0-P4：曼哈顿距离 = |0-7| + |0-0| = 7。先查根——
P0、P4 已经在同一组里，再连会成环 → 跳过这条边，费用不变（仍是 11）。
看边 P1-P4：曼哈顿距离 = |2-7| + |2-0| = 7。先查根——
P1、P4 已经在同一组里，再连会成环 → 跳过这条边，费用不变（仍是 11）。
看边 P1-P2：曼哈顿距离 = |2-3| + |2-10| = 9。这是当前最短的可用边，查两端的根——
根不同、不成环 → 选入这条边！两组并成一组（同色），累计费用 +9 = 20。已选 4/4 条。
看边 P2-P3：曼哈顿距离 = |3-5| + |10-2| = 10。先查根——
P2、P3 已经在同一组里，再连会成环 → 跳过这条边，费用不变（仍是 20）。
看边 P0-P2：曼哈顿距离 = |0-3| + |0-10| = 13。先查根——
P0、P2 已经在同一组里，再连会成环 → 跳过这条边，费用不变（仍是 20）。
看边 P2-P4：曼哈顿距离 = |3-7| + |10-0| = 14。先查根——
P2、P4 已经在同一组里，再连会成环 → 跳过这条边，费用不变（仍是 20）。
选满 4 条边，所有点连成一棵树（同一组同色）。最小总费用 = 20。这就是答案。
边界先想清。
两个高频追问。
参考代码
import java.util.*;class Solution { int[] parent; public int minCostConnectPoints(int[][] points) { int n = points.length; parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; List<int[]> edges = new ArrayList<>(); for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) { int w = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]); edges.add(new int[]{w, i, j}); } edges.sort((a, b) -> a[0] - b[0]); int cost = 0, used = 0; for (int[] e : edges) { int ra = find(e[1]), rb = find(e[2]); if (ra != rb) { parent[rb] = ra; cost += e[0]; used++; } if (used == n - 1) break; } return cost; } int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }}复杂度
- 时间：O(n²·log n)，n² 条边排序占主项，find 近乎常数
- 空间：O(n²)，要存所有点对的边
易错点
面试追问把动画讲成自己的话
追问为什么按边权从小到大就能得到最小生成树？
追问Kruskal 和 Prim 怎么选？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
网络延迟时间
LeetCode 743 · 中等 · 沿着 高级图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题