LC1584. 连接所有点的最小费用

Kruskal 最小生成树算法

def minCostConnectPoints(self, points):""":type points: List[List[int]]:rtype: int"""n = len(points)mp = []parent = list(range(n))for i in range(n):for j in range(i+1,n):mp.append((abs(points[i][0]-points[j][0]) + abs(points[i][1] - points[j][1]),i,j)) #把每个节点连接起来，并计算权重def find(x): #路径压缩，找根节点if x!= parent[x]:parent[x] = find(parent[x])return parent[x]def union(index1,index2): #两个集合合并parent[find(index1)] = find(index2)mp.sort() #最小生成树，用到贪心算法，先连接权重小的边cost = 0edges = 0for d,i,j in mp:if find(i) != find(j): #并查集判断，不能构成环union(i,j)cost += d edges += 1if edges == n-1:breakreturn cost

prim最小生成树算法

def minCostConnectPoints(self, points):""":type points: List[List[int]]:rtype: int"""n = len(points)mp = []visited = set() #记录已经访问的元素，在两个地方都要用到 def cut(i): #这里相当于找连接好的集合里的所有节点，与未连接的节点间的最短边for j in range(n):if j not in visited: #这两个节点间的边已经用过了，无需重复计算heapq.heappush(mp,(abs(points[i][0]-points[j][0]) + abs(points[i][1] - points[j][1]),j))mincost = 0cut(0) #从节点0开始visited.add(0) #记录访问while len(visited) != len(points): #所有节点都进行了连接d,node = heappop(mp) #找最短边if node in visited: #这个节点连接过了，下一个continuemincost += d #权重加起来cut(node) #前面节点集合里的对外边已经计算过了，计算最新加入的就行visited.add(node) #记录访问 return mincost

不用堆节约时间

def minCostConnectPoints(self, points: List[List[int]]) -> int:#Prim算法n = len(points)d = [float("inf")] * n # 表示各个顶点与加入最小生成树的顶点之间的最小距离.vis = [False] * n # 表示是否已经加入到了最小生成树里面d[0] = 0ans = 0for _ in range(n):# 寻找目前这轮的最小dM = float("inf") for i in range(n):if not vis[i] and d[i] < M:node = iM = d[i]vis[node] = Trueans += M# 更新与这个顶点相连接的顶点的d.for i in range(n):if not vis[i]:d[i] = min(d[i], abs(points[i][0] - points[node][0]) + abs(points[i][1] - points[node][1]))return ans

总结

以上是生活随笔为你收集整理的LC1584. 连接所有点的最小费用的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。