Prim算法
时间: 2023-07-10 18:12:01 浏览: 59
Prim算法是一种贪心算法,用于求解加权无向图的最小生成树。从一个节点开始,每次选择一个与当前生成树相邻的最小边,加入生成树中,直到所有节点都被加入生成树。下面是Prim算法的伪代码:
```
1. 选取一个起始节点u
2. 标记节点u为已访问
3. for v in u的邻居节点:
4. 将(u,v)加入候选边集合中
5. while 候选边集合不为空:
6. 从候选边集合中选择一条最小边(u,v),将v标记为已访问
7. 将(u,v)加入生成树中
8. for w in v的邻居节点:
9. 如果w未被访问过,将(v,w)加入候选边集合中
```
下面是一个示例代码,使用邻接矩阵来表示图:
```python
import sys
def prim(graph):
n = len(graph)
# 初始化
visited = [False] * n
dist = [sys.maxsize] * n
parent = [-1] * n
dist[0] = 0
for i in range(n):
# 找到未访问过的最近的节点
u = -1
for j in range(n):
if not visited[j] and (u == -1 or dist[j] < dist[u]):
u = j
# 标记为已访问
visited[u] = True
# 更新与节点u相邻的节点的距离
for v in range(n):
if not visited[v] and graph[u][v] != 0 and graph[u][v] < dist[v]:
dist[v] = graph[u][v]
parent[v] = u
return parent
# 示例代码
if __name__ == '__main__':
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 = prim(graph)
for i in range(1, len(parent)):
print("{}-{}".format(parent[i], i))
```
输出结果为:
```
0-1
1-2
0-3
1-4
```
其中,输出的每一行表示生成树中的一条边,如“0-1”表示0和1之间有一条边。