825344491

# 对Prim算法的个人理解 个人认为，对于Prim算法的理解，用教科书上的“加点”可以更好接受。设已被连入最小生成树的集合位MST，则每一次选取连接到MST中cost最小的点。因此优先队列里永远放的都是点和该点连接到MST需要的最小cost（其实也还是边的权值），然后随着算法的执行，每个点连接到MST的cost也会不断被更新（不断往优先级队列里插入更小的cost，原来的cost不会被删除）。这样想可以把Prim和Dijkstra完全类比，两个算法只有一行代码不同。 # 附1135和1584两题Python简洁Prim解法： ## 1135. 最低成本联通所有城市 ```python3 class Solution: def minimumCost(self, n: int, connections: List[List[int]]) -> int: graph = [[] for _ in range(n)] for connection in connections:...