求所示图的最小生成树prim算法python实现
时间: 2023-08-06 14:19:59 浏览: 47
好的,这是一个基于Prim算法的Python实现,用于求一个无向图的最小生成树:
```python
INF = float('inf')
def prim(graph):
n = len(graph)
visited = [False] * n
distance = [INF] * n
parent = [None] * n
distance[0] = 0
for _ in range(n):
# 选出当前未访问的节点中距离最小的节点
u = min((i for i in range(n) if not visited[i]), key=lambda x: distance[x])
visited[u] = True
# 遍历u的所有邻居节点
for v in range(n):
if graph[u][v] and not visited[v] and graph[u][v] < distance[v]:
distance[v] = graph[u][v]
parent[v] = u
# 输出最小生成树的边
for i in range(1, n):
print(parent[i], '-', i, ':', graph[i][parent[i]])
```
其中,`graph` 是一个邻接矩阵,表示无向图的边权重,若两个节点之间没有边,则权重为0。函数的输出结果是最小生成树的所有边及其权重。