Leetcode 1135. 最低成本连通所有城市

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.执行结果