代码随想录算法训练营 Day 49
Published:
最小生成树
最小生成树是所有节点的最小连通子图， 即：以最小的成本（边的权值）将图中所有节点链接到一起
Q1. KamaCoder 53
prim算法：
- 选距离生成树最近的节点
- 将节点加入到生成树中
- 更新非生成树节点到生成树的距离
if __name__ == '__main__':
v, e = map(int, input().split())
edge = [[10001] * (v + 1) for _ in range(v + 1)]
for _ in range(e):
n1, n2, weight = map(int, input().split())
edge[n1][n2] = weight
edge[n2][n1] = weight
visited = [False] * (v + 1)
min_dist = [10001] * (v + 1)
for _ in range(1, v + 1):
new_insert_node = -1
min_val = float('inf')
for j in range(1, v + 1):
if not visited[j] and min_dist[j] < min_val:
min_val = min_dist[j]
new_insert_node = j
visited[new_insert_node] = True
for j in range(1, v + 1):
if not visited[j] and min_dist[j] > edge[new_insert_node][j]:
min_dist[j] = edge[new_insert_node][j]
print(sum(min_dist[2:]))
Kruskal算法：判断是否在同一个集合中，就需要用到并查集
- 将所有的边按照权重进行排序
- 依次遍历所有边，如果边的两个顶点处于同一个集合中，说明不能加入这边，否则会形成环
- 如果边的两个顶点不处于同一个集合中，则将这条边加入到生成树中，并更新生成树中的权重和
class Edge:
def __init__(self, source, destination, weight):
self.s = source
self.d = destination
self.w = weight
class UnionFind:
def __init__(self, size):
self.parent = list(range(size + 1))
def find(self, u):
if u != self.parent[u]:
self.parent[u] = self.find(self.parent[u])
return self.parent[u]
def union(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u != root_v:
self.parent[root_v] = root_u
if __name__ == '__main__':
v, e = map(int, input().split())
edges = []
for _ in range(e):
n1, n2, weight = map(int, input().split())
edges.append(Edge(n1, n2, weight))
edges.sort(key=lambda x: x.w)
uf = UnionFind(v)
res = 0
for edge in edges:
x = uf.find(edge.s)
y = uf.find(edge.d)
if x != y:
res += edge.w
uf.union(x, y)
print(res)
总结
prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。因此稀疏图中，用Kruskal更优；在稠密图中，用prim算法更优。