1.题目基本信息
1.1.题目描述
想象一下你是个城市基建规划者,地图上有 n 座城市,它们按以 1 到 n 的次序编号。
给你整数 n 和一个数组 conections,其中 connections[i] = [x_i, y_i, cost_i] 表示将城市 x_i 和城市 y_i 连接所要的cost_i(连接是双向的)。
返回连接所有城市的最低成本,每对城市之间至少有一条路径。如果无法连接所有 n 个城市,返回 -1
该 最小成本 应该是所用全部连接成本的总和。
1.2.题目地址
https://leetcode.cn/problems/connecting-cities-with-minimum-cost/description/
2.解题方法
2.1.解题思路
Prim算法求最小生成树
2.2.解题步骤
第一步,构建图的邻接表
第二步,根据Prim算法模板算出最小生成树的节点和最小权值和,判断最小生成树是否存在并返回结果
3.解题代码
Python代码
import heapq
from typing import Dict,List
# ==> Prim算法模板:用于计算无向图的最小生成树及最小权值和
# graph:无向图的邻接表;item项例子:{节点:[[相邻边的权值,相邻边对面的节点],...],...}
# return:minWeightsSum为最小生成树的权值和;treeEdges为一个合法的最小生成树的边的列表(列表项:[节点,对面节点,两点之间的边的权值]);visited:为最小生成树的节点,可以用来判断图中是否存在最小生成树
def primMinSpanningTree(graph:Dict[object,List[List]]):
minWeightsSum,treeEdges=0,[]
firstNode=list(graph.keys())[0]
# 记录已经加入最小生成树的节点
visited=set([firstNode])
# 选择从firstNode开始,相邻的边加到堆中
neighEdgesHeap=[item+[firstNode] for item in graph[firstNode]]
heapq.heapify(neighEdgesHeap)
while neighEdgesHeap:
weight,node,node2=heapq.heappop(neighEdgesHeap) # node2为node的weight权值对应的边的对面的节点
if node not in visited: # 这个地方必须进行判断,否则会造成重复添加已访问节点,造成最小权值和偏大(因为前面遍历的节点可能将未遍历的共同相邻节点重复添加到堆中)
minWeightsSum+=weight
treeEdges.append([node,node2,weight])
visited.add(node)
# 遍历新访问的节点的边,加入堆中
for nextWeight,nextNode in graph[node]:
if nextNode not in visited:
heapq.heappush(neighEdgesHeap,[nextWeight,nextNode,node])
return minWeightsSum,treeEdges,visited
class Solution:
def minimumCost(self, n: int, connections: List[List[int]]) -> int:
# Prim算法
# 第一步,构建图的邻接表
graph={i+1:[] for i in range(n)}
for connection in connections:
graph[connection[0]].append([connection[2],connection[1]])
graph[connection[1]].append([connection[2],connection[0]])
# print(graph)
# 第二步,根据Prim算法模板算出最小生成树的节点和最小权值和,判断最小生成树是否存在并返回结果
minWeightsSum,_,nodes=primMinSpanningTree(graph)
return minWeightsSum if len(nodes)==n else -1
4.执行结果
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » Leetcode 1135. 最低成本连通所有城市
发表评论 取消回复