企业官网建设流程全解析

给你一些点，连接两点的代价不同。如何选尽量少的边，把所有点连成连通的整体，且总代价最小？

这就是最小生成树（Minimum Spanning Tree，MST）。

今天的主角LC.1584「连接所有点的最小费用」——平面上有n个点，连两点费用是曼哈顿距离，求连接所有点的最小总费用。

你会学到两把武器：

• Kruskal：所有边排序 + 并查集判环
• Prim：从一点出发，堆挑最小安全边

更妙的是，它把前面四周的积木全串起来了：并查集、堆、贪心思想——这是一次真正的“集大成”。

📦 题目速览 LeetCode1584（30 秒读懂）

给points[i] = [xi, yi]，连接两点费用是曼哈顿距离|xi-xj| + |yi-yj|。返回将所有点连通所需的最小总费用。

示例：

points = [[0,0],[2,2],[3,10],[5,2],[7,0]] 输出：20

一种最优连法：(0,0)-(2,2) 费4，(2,2)-(5,2) 费3，(5,2)-(7,0) 费4，(2,2)-(3,10) 费9，总=20

约束：n ≤ 1000，坐标 ≤ 1e6。

🧠 核心思路：切割性质 + 两种贪心实现

暴力为什么不行？

n个点要选n-1条边连成树，组合数爆炸。需要贪心策略保证“每次选的边都对”。

MST的理论基石：切割性质（Cut Property）

对任意把点集切成两半的“切割”，连接两个集合且权重最小的边，一定属于某个MST（叫“安全边”）。

换言之：每次安全地加一条“连接两个不同连通分量的最小边”，最终就得到MST。

两种算法只是“怎么找安全边”的方式不同。

Kruskal 算法（O(ElogE)）——并查集登场

1. 把所有边按权重从小到大排序
2. 依次考察每条边，若两端不在同一连通分量（用并查集find判断），就选它（union合并），累加费用
3. 若已在同一分量，加了会成环，跳过
4. 选满n-1条边即停

并查集在这里干的就是“判环/查连通”的脏活，单次近乎O(α(n))。

Prim算法（O(ElogV)）——堆登场

从任意一个点开始，维护“已连通集合”，用优先队列每次挑“从已连通集合伸向未连通点的最小边”加入，把新点并入集合。重复到所有点都在集合里。

它像 Dijkstra的孪生：Dijkstra堆里存“(到起点距离, 节点)”，Prim堆里存“(到已连通集合的最小边权, 节点)”，扩张方式几乎一样。

两算法怎么选？

• 稀疏图（E 小）用Kruskal：代码最短，天然用并查集
• 稠密图（E≈V²）用Prim：邻接矩阵 + 朴素O(V²)实现时更优

本题点少（n≤1000），所有点对都是候选边，Kruskal排序O(V²logV) 完全可接受。

🖼️ 图解算法（手把手走一遍）

以示例5点演示 Kruskal：

各点：A(0,0) B(2,2) C(3,10) D(5,2) E(7,0) 边权排序（前几条）： B-D=3, A-B=4, D-E=4, A-D=7, A-E=7, B-E=7, B-C=9, C-D=10, A-C=13, C-E=14

关键观察：每选一条边前都先find两端——只有“跨分量”才选，“同分量”一律跳过（避免成环）。这正是并查集在MST里的核心职责。

💻 代码实现（Python + Java）

Python版（Kruskal + Prim双写法）

importheapqclassSolution:# ---------- Kruskal：排序边 + 并查集判环 ----------defminCostConnectPoints(self,points:List[List[int]])->int:n=len(points)edges=[]foriinrange(n):forjinrange(i+1,n):d=abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])edges.append((d,i,j))edges.sort()# ① 边按权升序parent=list(range(n))deffind(x):# ② 路径压缩whilex!=parent[x]:parent[x]=parent[parent[x]];x=parent[x]returnx cost=0ford,i,jinedges:# ③ 贪心选安全边iffind(i)!=find(j):# 跨分量 = 安全边parent[find(i)]=find(j)cost+=dreturncost# ---------- Prim：堆不断吞并最近的点 ----------defminCostConnectPointsPrim(self,points:List[List[int]])->int:n=len(points)adj=[[]for_inrange(n)]foriinrange(n):forjinrange(i+1,n):d=abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])adj[i].append((d,j));adj[j].append((d,i))visited=[False]*n pq=[(0,0)]# (到已连通集合的最小边权, 节点)total=0whilepq:w,u=heapq.heappop(pq)ifvisited[u]:continue# 过期条目跳过visited[u]=Truetotal+=wforw2,vinadj[u]:ifnotvisited[v]:heapq.heappush(pq,(w2,v))returntotal

Java版（Kruskal）

classSolution{privateint[]parent;publicintminCostConnectPoints(int[][]points){intn=points.length;int[][]edges=newint[n*(n-1)/2][3];intidx=0;for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){intd=Math.abs(points[i][0]-points[j][0])+Math.abs(points[i][1]-points[j][1]);edges[idx++]=newint[]{d,i,j};}}Arrays.sort(edges,(a,b)->a[0]-b[0]);parent=newint[n];for(inti=0;i<n;i++)parent[i]=i;intcost=0;for(int[]e:edges){intd=e[0],i=e[1],j=e[2];intri=find(i),rj=find(j);if(ri!=rj){parent[ri]=rj;cost+=d;}}returncost;}privateintfind(intx){while(x!=parent[x]){parent[x]=parent[parent[x]];x=parent[x];}returnx;}}

⚠️防坑提醒（必看）：

• Kruskal必须先建全边再sort，否则贪心顺序错。
• find(i) != find(j)是“判安全边”的唯一判据——同根即同分量、会成环。
• Prim 的堆里存(边权, 节点)，用visited防重复计入。
• 两算法结果恒等（MST总权唯一，尽管边选法可能不唯一）。

⏱️ 复杂度分析（面试必问）

本题同阶，Kruskal代码更短、更易写对，面试首选。

🚀 举一反三：4 道高频变体题

💬 面试追问模拟（提前准备，惊艳全场）

Q1：Kruskal和Prim适用场景怎么对比？

稀疏图（E远小于V²）选Kruskal（O(ElogE)，代码最短）；
稠密图（E≈V²）选Prim，尤其邻接矩阵 + 朴素O(V²) 实现优于Kruskal的O(V²logV)。
另外Kruskal需要“先拿到所有边并排序”，边是流式到来或不便枚举时Prim更顺。

Q2：为什么MST用并查集判环（Kruskal）？

Kruskal逐边加入，加边前必须确认“两端是否已连通”——这恰是并查集的强项：find(i)==find(j)即同分量（加了会成环），union即合并。单次近乎O(α(n))，比每次DFS查连通快得多。

Q3：第二小生成树怎么想？

MST总权唯一，但“严格第二小”需要：枚举每条不在MST里的边e，加入后会与MST形成环，去掉环上权重最大的边（且 ≠ e自身），得到一棵新树；所有候选里取总权次小者。本质是“换边”思想。

🧩 实战小技巧（刷题党必备）

• 口诀：Kruskal排序边，并查集判环；Prim用堆，每次吞最近。
• 模板：Kruskal = 建边 + 排序 + 并查集；Prim = 邻接表 + 优先队列 + visited。
• 防坑：Kruskal选满n-1条边即停；Prim用visited防重复。

📈 实际应用场景（不止是刷题）

• 城市/校园光缆布线：用最少线缆连通所有楼
• 电力/供水管网规划：最低成本连通
• 通信基站骨干网：最少链路连接
• 聚类分析：用边权表达相似度，MST做层次聚类切分
• 芯片引脚连线优化：最短布线

🎁 今日思考题

如果面试官把 LC.1584的“曼哈顿距离”换成“欧几里得距离”，代码要改哪一行？
提示：只需改距离计算那一行，其余逻辑完全不变。

Kruskal和Prim你更想先背哪个？