1.题目基本信息
1.1.题目描述
给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [x_i, y_i] 。
连接点 [x_i, y_i] 和点 [x_j, y_j] 的费用为它们之间的 曼哈顿距离 ：|x_i – x_j| + |y_i – y_j| ，其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
1.2.题目地址
https://leetcode.cn/problems/min-cost-to-connect-all-points/description/
2.解题方法
2.1.解题思路
最小生成树+Prim算法/Kruskal算法
2.2.解题步骤
Kruskal算法
- 第一步，构建边的堆
- 第二步，构建并查集并初始化节点
- 第三步，从堆中弹出(节点数-1)条非内联边加到并查集中
Prim算法
- 第一步，构建有向图
- 第二步，Prim算法构建最小生成树并获取其权值和
3.解题代码
Python代码（Kruskal算法）（附并查集模板）
# # ==> 并查集模板(附优化)
class UnionFind():def __init__(self):self.roots={}self.setCnt=0 # 连通分量的个数# Union优化:存储根节点主导的集合的总节点数self.rootSizes={}def add(self,x):if x not in self.roots:self.roots[x]=xself.rootSizes[x]=1self.setCnt+=1def find(self,x):root=xwhile root != self.roots[root]:root=self.roots[root]# 优化:压缩路径while x!=root:temp=self.roots[x]self.roots[x]=rootx=tempreturn rootdef union(self,x,y):rootx,rooty=self.find(x),self.find(y)if rootx!=rooty:# 优化:小树合并到大树上if self.rootSizes[rootx]<self.rootSizes[rooty]:self.roots[rootx]=rootyself.rootSizes[rooty]+=self.rootSizes[rootx]else:self.roots[rooty]=rootxself.rootSizes[rootx]+=self.rootSizes[rooty]self.setCnt-=1import heapq
class Solution:# Kruskal算法def minCostConnectPoints(self, points: List[List[int]]) -> int:pcnt=len(points)# 构建边的堆edgesHeap=[]for i in range(pcnt):for j in range(i+1,pcnt):dist=abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])heapq.heappush(edgesHeap,(dist,i,j))# 构建并查集并初始化节点uf=UnionFind()for i in range(pcnt):uf.add(i)# 从堆中弹出(节点数-1)条非内联边加到并查集中addedEdgesCnt=0minTotalWeight=0while addedEdgesCnt<pcnt-1:weight,node1,node2=heapq.heappop(edgesHeap)if uf.find(node1)!=uf.find(node2):uf.union(node1,node2)minTotalWeight+=weightaddedEdgesCnt+=1return minTotalWeight
Python代码（附Prim算法模板）
import heapq
from typing import Dict,List
# ==> Prim算法模板：用于计算无向图的最小生成树及最小权值和
# graph:无向图的邻接表；item项例子：{节点:[[相邻边的权值,相邻边对面的节点],...],...}
# return:minWeightsSum为最小生成树的权值和；treeEdges为一个合法的最小生成树的边的列表（列表项：[节点,对面节点,两点之间的边的权值]）；visited为最小生成树的节点，可以用来判断图中是否存在最小生成树
def primMinSpanningTree(graph:List[List[List]]):minWeightsSum,treeEdges=0,[]firstNode=0# 记录已经加入最小生成树的节点visited=set([firstNode])# 选择从firstNode开始，相邻的边加到堆中neighEdgesHeap=[item+[firstNode] for item in graph[firstNode]]heapq.heapify(neighEdgesHeap)while neighEdgesHeap:weight,node,startNode=heapq.heappop(neighEdgesHeap) # node2为node的weight权值对应的边的对面的节点if node in visited: # 这个地方必须进行判断，否则会造成重复添加已访问节点，造成最小权值和偏大（因为前面遍历的节点可能将未遍历的共同相邻节点重复添加到堆中）continueminWeightsSum+=weighttreeEdges.append([startNode,node,weight])visited.add(node)# 遍历新访问的节点的边，加入堆中for nextWeight,nextNode in graph[node]:if nextNode not in visited:heapq.heappush(neighEdgesHeap,[nextWeight,nextNode,node])return minWeightsSum,treeEdges,visitedclass Solution:# Prim算法def minCostConnectPoints(self, points: List[List[int]]) -> int:pcnt=len(points)# 第一步，构建有向图graph=[[] for i in range(pcnt)]for i in range(pcnt):for j in range(i+1,pcnt):dist=abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])graph[i].append([dist,j])graph[j].append([dist,i])# print(graph)# 第二步，Prim算法构建最小生成树并获取其权值和minTotalDist,_,_=primMinSpanningTree(graph)# print(minTotalDist)return minTotalDist
4.执行结果
