labuladong
Prim 最小生成树算法 :: labuladong的算法小抄
1135 题「 最低成本联通所有城市」，Prim算法的python实现
import heapq
import collections
class Solution:
# Kruscal并查集方式判定
class UnionFind(object):
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, x1, x2):
self.parent[self.find(x1)] = self.find(x2)
def connected(self, x1, x2):
return self.find(x1) == self.find(x2)
def minCostConnectPoints(self, points: List[List[int]]) -> int:
# 连边权重换成了曼哈顿距离
def manhattan_distance(p1, p2):
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
# 1.uf并查集解决方案
n = len(points)
# uf = Solution.UnionFind(n)
# # 遍历构建点之间距离数组
distances = []
for i in range(n):
for j in range(i, n):
distances.append(
(i, j, manhattan_distance(points[i], points[j])))
# distances = sorted(distances, key=lambda x: x[-1])
# count = 0
# for dist in distances:
# x, y, x_y_dist = dist
# if uf.connected(x, y):
# continue
# uf.union(x, y)
# count += x_y_dist
# return count
# 2.BFS方式
def build_graph(connections): # 构建图
graph = collections.defaultdict(list)
# 无向图就是双向图
for conn in connections:
u, v, weight = conn
graph[u].append((u, v, weight))
graph[v].append((v, u, weight))
return graph
def cut(s):
for edge in graph[s]:
_from, _to, weight = edge
if in_mst[_to]:
continue
heapq.heappush(pq, (weight, _from, _to))
graph = build_graph(distances)
pq = []
# 记录MST中的节点
in_mst = [False] * n
# 记录最终结果
weight_sum = 0
in_mst[0] = True
cut(0)
while pq:
weight, _from, _to = heapq.heappop(pq)
if in_mst[_to]:
continue
weight_sum += weight
in_mst[_to] = True
cut(_to)
return weight_sum
“Prim 算法的时间复杂度也是可以优化的，但优化点在于优先级队列的实现上” 能优于O(ElogE)吗？网上好像都是从array优化成priorityqueue，好像没有更优化的了
@JerryWuZiJie priorityqueue 也有不同的实现，有些实现可以直接修改队列中的元素，这样的优先级队列可以进一步降低时间复杂度。Java 标准库的优先级队列不可以。
对Prim算法的个人理解
个人认为，对于Prim算法的理解，用教科书上的“加点”可以更好接受。设已被连入最小生成树的集合位MST，则每一次选取连接到MST中cost最小的点。因此优先队列里永远放的都是点和该点连接到MST需要的最小cost（其实也还是边的权值），然后随着算法的执行，每个点连接到MST的cost也会不断被更新（不断往优先级队列里插入更小的cost，原来的cost不会被删除）。这样想可以把Prim和Dijkstra完全类比，两个算法只有一行代码不同。
附1135和1584两题Python简洁Prim解法：
1135. 最低成本联通所有城市
class Solution:
def minimumCost(self, n: int, connections: List[List[int]]) -> int:
graph = [[] for _ in range(n)]
for connection in connections:
graph[connection[0] - 1].append((connection[2], connection[1] - 1))
graph[connection[1] - 1].append((connection[2], connection[0] - 1))
heap = [(0, 0)]
mst = set()
cost = 0
while heap:
cur = heapq.heappop(heap)
if cur[1] not in mst:
mst.add(cur[1])
cost += cur[0]
for vertex in graph[cur[1]]:
heapq.heappush(heap, vertex)
if len(mst) == n:
return cost
return -1
1584. 连接所有点的最小费用
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
n = len(points)
graph = [[] for _ in range(n)]
for i in range(n - 1):
for j in range(i + 1, n):
graph[i].append((abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), j))
graph[j].append((abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), i))
heap = [(0, 0)]
mst = set()
cost = 0
while heap:
cur = heapq.heappop(heap)
if cur[1] not in mst:
mst.add(cur[1])
cost += cur[0]
for vertex in graph[cur[1]]:
heapq.heappush(heap, vertex)
if len(mst) == n:
return cost
cut({A, B, C}) = cut({A, B}) + cut({C}) - [cut({A,B}) ^cut({B}) ]，这样才对吧，减去它俩的交集
cut({A, B, C}) = cut({A, B}) + cut({C}) - [cut({A,B}) ^cut({C}) ]，这样才对吧，减去它俩的交集, 刚写错了