prime算法代码讲解
时间: 2023-11-12 19:29:16 浏览: 40
Prime算法是一种用于求解最小生成树的贪心算法,它的基本思想是:从任意一个节点开始,选择与该节点相邻的边中最小的一条,将该边所连接的节点加入到生成树中,然后再从与新加入的节点相邻的边中选择最小的一条,重复此过程直到所有的节点都被加入到生成树中为止。
以下是Prime算法的代码实现(假设图G以邻接矩阵的形式表示):
```python
def prim(G, s):
"""
:param G: 图G,以邻接矩阵的形式表示
:param s: 起始节点
:return: 生成树
"""
n = len(G)
INF = float('inf')
visited = [False] * n # 记录节点是否已被访问
dist = [INF] * n # 记录每个节点到生成树的距离
dist[s] = 0 # 起始节点到生成树的距离为0
parent = [-1] * n # 记录每个节点的父节点,用于构建生成树
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
# 更新与新加入节点相邻的节点到生成树的距离
for v in range(n):
if not visited[v] and G[u][v] != INF and G[u][v] < dist[v]:
dist[v] = G[u][v]
parent[v] = u
# 构建生成树
tree = [[] for _ in range(n)]
for i in range(n):
if parent[i] != -1:
tree[parent[i]].append(i)
tree[i].append(parent[i])
return tree
```
该算法的时间复杂度为O(N^2),其中N为节点的数量。