高频必考！最小生成树：并查集 + 堆 + 贪心，一次收进MST

给你一些点连接两点的代价不同。如何选尽量少的边把所有点连成连通的整体且总代价最小这就是最小生成树Minimum Spanning TreeMST。今天的主角LC.1584「连接所有点的最小费用」——平面上有n个点连两点费用是曼哈顿距离求连接所有点的最小总费用。你会学到两把武器Kruskal所有边排序 并查集判环Prim从一点出发堆挑最小安全边更妙的是它把前面四周的积木全串起来了并查集、堆、贪心思想——这是一次真正的“集大成”。 题目速览 LeetCode158430 秒读懂给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)——并查集登场把所有边按权重从小到大排序依次考察每条边若两端不在同一连通分量用并查集find判断就选它union合并累加费用若已在同一分量加了会成环跳过选满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-D3, A-B4, D-E4, A-D7, A-E7, B-E7, B-C9, C-D10, A-C13, C-E14顺序考察边两端是否同分量动作累计费用已选边1B-D(3)否选union(B,D)3B-D2A-B(4)否选union(A,{B,D})7A-B, B-D3D-E(4)否(E独立)选union(E,…)11D-E4A-D(7)是(A、D同分量)跳过成环11—5A-E(7)是跳过11—6B-E(7)是跳过11—7B-C(9)否(C 独立)选union(C,…)20B-C—已选 4 条边 n-1全连通停止20 ✅—关键观察每选一条边前都先find两端——只有“跨分量”才选“同分量”一律跳过避免成环。这正是并查集在MST里的核心职责。 代码实现Python JavaPython版Kruskal Prim双写法importheapqclassSolution:# ---------- Kruskal排序边 并查集判环 ----------defminCostConnectPoints(self,points:List[List[int]])-int:nlen(points)edges[]foriinrange(n):forjinrange(i1,n):dabs(points[i][0]-points[j][0])abs(points[i][1]-points[j][1])edges.append((d,i,j))edges.sort()# ① 边按权升序parentlist(range(n))deffind(x):# ② 路径压缩whilex!parent[x]:parent[x]parent[parent[x]];xparent[x]returnx cost0ford,i,jinedges:# ③ 贪心选安全边iffind(i)!find(j):# 跨分量 安全边parent[find(i)]find(j)costdreturncost# ---------- Prim堆不断吞并最近的点 ----------defminCostConnectPointsPrim(self,points:List[List[int]])-int:nlen(points)adj[[]for_inrange(n)]foriinrange(n):forjinrange(i1,n):dabs(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)]# (到已连通集合的最小边权, 节点)total0whilepq:w,uheapq.heappop(pq)ifvisited[u]:continue# 过期条目跳过visited[u]Truetotalwforw2,vinadj[u]:ifnotvisited[v]:heapq.heappush(pq,(w2,v))returntotalJava版KruskalclassSolution{privateint[]parent;publicintminCostConnectPoints(int[][]points){intnpoints.length;int[][]edgesnewint[n*(n-1)/2][3];intidx0;for(inti0;in;i){for(intji1;jn;j){intdMath.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]);parentnewint[n];for(inti0;in;i)parent[i]i;intcost0;for(int[]e:edges){intde[0],ie[1],je[2];intrifind(i),rjfind(j);if(ri!rj){parent[ri]rj;costd;}}returncost;}privateintfind(intx){while(x!parent[x]){parent[x]parent[parent[x]];xparent[x];}returnx;}}⚠️防坑提醒必看Kruskal必须先建全边再sort否则贪心顺序错。find(i) ! find(j)是“判安全边”的唯一判据——同根即同分量、会成环。Prim 的堆里存(边权, 节点)用visited防重复计入。两算法结果恒等MST总权唯一尽管边选法可能不唯一。⏱️ 复杂度分析面试必问算法时间空间适用KruskalO(ElogE)O(VE)稀疏图Prim堆O(ElogV)O(VE)稠密图略优Prim朴素O(V²)O(V²)稠密图最优本题同阶Kruskal代码更短、更易写对面试首选。 举一反三4 道高频变体题题目变化点思路要点LC.1135 最低成本连通所有城市直接给边列表标准KruskalLC.1168 水资源分配虚拟源点 Kruskal加一个“水井”超级节点LC.1489 找到最小生成树里的关键边和伪关键边MST边分类枚举每条边分别强制选/不选再跑MST第二小生成树换一条MST边试试枚举每条非树边替换环上最大边 面试追问模拟提前准备惊艳全场Q1Kruskal和Prim适用场景怎么对比稀疏图E远小于V²选KruskalO(ElogE)代码最短稠密图E≈V²选Prim尤其邻接矩阵 朴素O(V²) 实现优于Kruskal的O(V²logV)。另外Kruskal需要“先拿到所有边并排序”边是流式到来或不便枚举时Prim更顺。Q2为什么MST用并查集判环KruskalKruskal逐边加入加边前必须确认“两端是否已连通”——这恰是并查集的强项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你更想先背哪个