prim算法最小生成树伪代码实现

以下是prim算法的最小生成树伪代码实现：

输入：无向图G，节点数n，边数m，表示第i个节点是否已加入集合的数组vis，节点之间的边的权值数组w。

1.选择1号节点作为初始节点加入集合，vis[1]=true。

2.初始化dist数组，dist[i]=w[1][i]，表示与1号节点相连的边的权值。

3.重复执行n-1次以下操作：

1)从未加入集合的节点中找到dist最小的节点v，将其加入集合，vis[v]=true。

2)更新未加入集合的节点与集合中节点的边的权值，若dist[i]>w[v][i]，则dist[i]=w[v][i]。

4.输出最小生成树的总权值sum，由vis数组可以得到最小生成树的节点集合。

伪代码如下：

prim(G, n, m, vis, w):
# 选择1号节点作为初始节点加入集合
vis[1] = true
# 初始化dist数组
for i in range(2, n+1):
dist[i] = w[1][i]
# 重复执行n-1次
for i in range(1, n):
# 找到dist最小的节点v，将其加入集合
minDist = INF
for j in range(1, n+1):
if not vis[j] and dist[j] < minDist:
minDist = dist[j]
v = j
vis[v] = true
# 更新dist数组
for j in range(1, n+1):
if not vis[j] and dist[j] > w[v][j]:
dist[j] = w[v][j]
# 计算最小生成树的总权值
sum = 0
for i in range(1, n+1):
if vis[i]:
sum += dist[i]
return sum