最小生成树算法python代码
时间: 2023-10-03 09:08:34 浏览: 69
下面是使用 Prim 算法实现最小生成树的 Python 代码:
```python
INF = float('inf')
def prim(graph):
n = len(graph)
selected = [False] * n
dist = [INF] * n
dist[0] = 0
for _ in range(n):
u = -1
for i in range(n):
if not selected[i] and (u == -1 or dist[i] < dist[u]):
u = i
selected[u] = True
for v, w in graph[u]:
if not selected[v] and w < dist[v]:
dist[v] = w
return sum(dist)
# 测试
graph = [
[(1, 5), (2, 1)],
[(0, 5), (2, 2), (3, 1)],
[(0, 1), (1, 2), (3, 4)],
[(1, 1), (2, 4)]
]
print(prim(graph)) # 输出 5
```
上述代码中,`graph` 是一个邻接表表示的图,其中 `graph[i]` 是一个列表,表示顶点 `i` 的邻居,列表中每个元素是一个二元组 `(v, w)`,表示顶点 `i` 与顶点 `v` 之间有一条权重为 `w` 的边。`prim` 函数返回最小生成树的权重和。
相关推荐
![](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)