使用普利姆算法计算最小生成树代码
时间: 2023-07-22 21:09:08 浏览: 61
好的,下面是使用普利姆算法计算最小生成树的代码示例,假设我们有一个邻接矩阵 graph 表示图的结构和边的权值:
```python
import heapq
def prim(graph):
n = len(graph)
visited = [False] * n
mst = []
heap = []
# 从节点0开始,将其加入最小生成树集合
visited[0] = True
for j in range(n):
if graph[0][j] != 0:
heapq.heappush(heap, (graph[0][j], 0, j))
# 遍历所有节点
while len(mst) < n-1 and heap:
# 找到当前最小边
w, u, v = heapq.heappop(heap)
if visited[u] and visited[v]:
continue
# 将其加入最小生成树
mst.append((u, v, w))
# 将与新节点相邻的边加入堆中
if not visited[u]:
visited[u] = True
for j in range(n):
if graph[u][j] != 0:
heapq.heappush(heap, (graph[u][j], u, j))
if not visited[v]:
visited[v] = True
for j in range(n):
if graph[v][j] != 0:
heapq.heappush(heap, (graph[v][j], v, j))
return mst
```
在这段代码中,我们使用了 Python 内置的 heapq 模块来实现堆的功能,其中 heap 列表用于存储当前与最小生成树相邻的边。在遍历过程中,我们不断从 heap 中取出权值最小的边,将其加入最小生成树中,并将其相邻的边加入 heap 中。在加入新的边时,我们需要判断其连接的两个节点是否已经在最小生成树集合中,以避免出现环的情况。