prim算法求最小生成树m
时间: 2023-12-23 17:04:26 浏览: 30
以下是Prim算法求最小生成树的步骤和代码实现:
1. 朴素Prim算法步骤:
- 选择一个起始顶点作为生成树的根节点。
- 将该顶点加入生成树的集合。
- 从生成树的集合中选择一条边,该边的两个顶点一个在生成树的集合中,一个不在。
- 选择这些边中权值最小的边,并将该边的另一个顶点加入生成树的集合。
- 重复上述步骤,直到生成树的集合包含所有顶点。
2. 堆优化Prim算法步骤:
- 选择一个起始顶点作为生成树的根节点。
- 将该顶点加入生成树的集合,并将与该顶点相邻的边加入最小堆中。
- 从最小堆中选择一条权值最小的边,如果该边的另一个顶点不在生成树的集合中,则将该边加入生成树,并将与该顶点相邻的边加入最小堆中。
- 重复上述步骤,直到生成树的集合包含所有顶点。
3. 代码实现:
- 朴素Prim的代码实现:
```python
def prim(graph):
n = len(graph)
visited = [False] * n
visited[0] = True
edges = []
while len(edges) < n - 1:
min_weight = float('inf')
u, v = -1, -1
for i in range(n):
if visited[i]:
for j in range(n):
if not visited[j] and graph[i][j] < min_weight:
min_weight = graph[i][j]
u, v = i, j
edges.append((u, v))
visited[v] = True
return edges
```
- 堆优化Prim的代码实现:
```python
import heapq
def prim(graph):
n = len(graph)
visited = [False] * n
visited[0] = True
edges = []
heap = []
for i in range(1, n):
heapq.heappush(heap, (graph[0][i], 0, i))
while len(edges) < n - 1:
weight, u, v = heapq.heappop(heap)
if visited[v]:
continue
edges.append((u, v))
visited[v] = True
for i in range(n):
if not visited[i]:
heapq.heappush(heap, (graph[v][i], v, i))
return edges
```