python普里姆算法
时间: 2023-11-30 17:43:00 浏览: 40
以下是Python实现Prim算法的示例:
```python
INF = 9999999
# 顶点数
V = 5
# 从图中选择最小距离的顶点
def minKey(key, mstSet):
min = INF
for v in range(V):
if key[v] < min and mstSet[v] == False:
min = key[v]
min_index = v
return min_index
# 打印最小生成树
def printMST(parent, graph):
print("Edge \tWeight")
for i in range(1, V):
print(parent[i], "-", i, "\t", graph[i][parent[i]])
# 构建最小生成树
def primMST(graph):
# 存储最小生成树的父节点
parent = [None] * V
# 存储每个顶点到最小生成树的距离
key = [INF] * V
# 标记顶点是否已经被加入最小生成树
mstSet = [False] * V
# 从第一个顶点开始
key[0] = 0
parent[0] = -1
for cout in range(V):
# 选择距离最小的顶点
u = minKey(key, mstSet)
# 将该顶点加入最小生成树
mstSet[u] = True
# 更新与该顶点相邻的顶点的距离
for v in range(V):
if graph[u][v] > 0 and mstSet[v] == False and key[v] > graph[u][v]:
key[v] = graph[u][v]
parent[v] = u
printMST(parent, graph)
# 测试
graph = [[0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]]
primMST(graph)
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)