prim算法求最小生成树py
时间: 2023-11-04 12:06:03 浏览: 57
下面是使用Prim算法求解最小生成树的Python实现:
```python
# 定义Prim算法函数
def prim(graph):
"""
graph: 二维数组,表示图的邻接矩阵
"""
n = len(graph) # 图中节点的个数
# 初始化相关变量
low_cost = [float('inf')] * n # 保存当前节点到最小生成树的最小距离
closest = [0] * n # 保存当前节点到最小生成树中距离最近的节点的编号
selected = [False] * n # 标记节点是否已经被加入到最小生成树中
# 从第一个节点开始构建最小生成树
low_cost[0] = 0
for i in range(n):
# 找到当前节点到最小生成树中距离最近的节点
min_dist = float('inf')
for j in range(n):
if not selected[j] and low_cost[j] < min_dist:
min_dist = low_cost[j]
k = j
selected[k] = True
# 更新其他未加入最小生成树的节点距离最小生成树的距离和closest数组
for j in range(n):
if not selected[j] and graph[k][j] < low_cost[j]:
low_cost[j] = graph[k][j]
closest[j] = k
# 构建最小生成树
edges = []
for i in range(1, n):
edges.append((closest[i], i, graph[closest[i]][i]))
return edges
```
其中,`graph`是输入的邻接矩阵,返回值为最小生成树的边集合。