编写一个程序,实现求解带权连通图中最小生成树的算法
时间: 2024-02-05 12:12:04 浏览: 90
我们可以使用Prim算法或Kruskal算法来求解带权连通图中最小生成树。
以下是Prim算法的Python实现:
```
import heapq
def prim(graph):
# 初始化
mst = {}
visited = [False] * len(graph)
heap = [(0, 0)] # (权重, 节点)
while heap:
weight, node = heapq.heappop(heap)
if visited[node]:
continue
visited[node] = True
mst[node] = weight
for neighbor, weight in graph[node]:
if not visited[neighbor]:
heapq.heappush(heap, (weight, neighbor))
return mst
```
其中,graph表示带权连通图,每个节点表示为一个数字,每个节点的邻居表示为一个二元组(邻居节点, 权重)的列表。该算法使用一个最小堆来存储当前所有可用的边,每次从堆中取出权重最小的边,将其加入最小生成树中,并将该边所连接的节点加入堆中。
以下是Kruskal算法的Python实现:
```
def kruskal(graph):
# 初始化
mst = {}
parent = [i for i in range(len(graph))]
rank = [0] * len(graph)
edges = []
# 将所有边加入堆中
for node in range(len(graph)):
for neighbor, weight in graph[node]:
edges.append((weight, node, neighbor))
# 根据边的权重排序
edges.sort()
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px != py:
if rank[px] > rank[py]:
parent[py] = px
else:
parent[px] = py
if rank[px] == rank[py]:
rank[py] += 1
# 遍历所有边,加入最小生成树
for weight, node1, node2 in edges:
if find(node1) != find(node2):
union(node1, node2)
mst[node1] = weight
return mst
```
其中,graph表示带权连通图,每个节点表示为一个数字,每个节点的邻居表示为一个二元组(邻居节点, 权重)的列表。该算法使用并查集来维护当前已连接的节点,每次选择权重最小的边,如果该边的两个节点不在同一个集合中,则将它们连接起来,并将该边加入最小生成树中。
阅读全文