python prim算法
时间: 2024-03-31 18:31:22 浏览: 27
Prim算法是一种用于解决最小生成树问题的贪心算法。最小生成树是指在一个连通无向图中,找到一个子图,使得该子图包含了原图中的所有顶点,并且边的权重之和最小。
Python中可以使用Prim算法来求解最小生成树。下面是Prim算法的基本步骤:
1. 选择一个起始顶点作为生成树的根节点,并将其加入生成树中。
2. 从与生成树相邻的顶点中选择一个权重最小的边,并将其加入生成树中。
3. 重复上述步骤,直到生成树包含了原图中的所有顶点。
在Python中,可以使用邻接矩阵或邻接表来表示图。以下是使用邻接矩阵表示图并实现Prim算法的示例代码:
```python
import sys
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]
def min_key(self, key, mst_set):
min_val = sys.maxsize
min_index = -1
for v in range(self.V):
if key[v] < min_val and not mst_set[v]:
min_val = key[v]
min_index = v
return min_index
def prim_mst(self):
key = [sys.maxsize] * self.V
parent = [None] * self.V
key[0] = 0
mst_set = [False] * self.V
for _ in range(self.V):
u = self.min_key(key, mst_set)
mst_set[u] = True
for v in range(self.V):
if self.graph[u][v] > 0 and not mst_set[v] and key[v] > self.graph[u][v]:
key[v] = self.graph[u][v]
parent[v] = u
return parent
# 示例用法
g = Graph(5)
g.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]]
parent = g.prim_mst()
print("边\t权重")
for i in range(1, g.V):
print(parent[i], "-", i, "\t", g.graph[i][parent[i]])
```
这段代码中,我们首先定义了一个Graph类,其中包含了图的顶点数和邻接矩阵。然后,我们实现了prim_mst方法来执行Prim算法。最后,我们创建了一个示例图,并打印出最小生成树的边及其权重。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)