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

A：

1. 选择任意一个起始点作为生成树的根节点
2. 将所有与根节点相邻的边加入候选边集中(候选边集初始化)
3. 选择候选边集中权重最小的边，如果该边连接的节点未被加入生成树，就将该边和节点加入生成树，同时将连接该节点的边加入候选边集中
4. 重复步骤3，直到候选边集为空

伪代码如下：

1. MST-Prim(G, r):
2. for each vertex v in G.V:
3. v.key = infinity # 顶点v的关键字，表示与生成树中的最小边权重
4. v.parent = NIL # v的父节点
5. r.key = 0 # 随机选择一个顶点r的权值设置为0，作为起点
6. Q = G.V # Q为集合，包含所有顶点
7. while Q is not empty:
8. u = Extract-Min(Q) # 取出key值最小的顶点
9. for each v in G.Adj[u]: # 对u的邻接点v进行松弛操作
10. if v in Q and G.weight(u,v) < v.key:
11. v.parent = u # 当前v的父亲是u
12. v.key = G.weight(u,v) # 更新v的关键字
13. return MST(G) # 返回最小生成树的所有边