用python写一个求最小生成树prim算法代码
时间: 2023-11-10 10:06:19 浏览: 46
当然可以,以下是基于 Python 的 Prim 算法代码实现。
```python
import heapq
def prim(graph):
"""
Prim's algorithm to find minimum spanning tree of a graph.
"""
visited = set()
edges = [(0, None, graph.keys()[0])]
mst = []
while edges:
weight, prev, node = heapq.heappop(edges)
if node not in visited:
visited.add(node)
mst.append((prev, node, weight))
for neighbor, w in graph[node].items():
if neighbor not in visited:
heapq.heappush(edges, (w, node, neighbor))
return mst
```
其中,使用了 Python 自带的 `heapq` 模块来实现最小堆,优化了 Prim 算法的时间复杂度。
输入的 `graph` 参数是一个字典,其中键是节点,值是另一个字典,表示邻居和它们之间的权重。这可以通过以下方式创建:
```python
graph = {
'A': {'B': 2, 'C': 3, 'D': 1},
'B': {'A': 2, 'E': 3},
'C': {'A': 3, 'E': 1},
'D': {'A': 1},
'E': {'B': 3, 'C': 1}
}
```
最后,返回一个列表,其中每个元素都是一个三元组,表示连接两个顶点的边和它们之间的权重。