prim算法堆优化算法伪码

以下是使用堆优化的 Prim 算法伪代码：

Input: 一个带权重的无向图 G=(V,E)，其中 V 是节点集合，E 是边集合
Output: 一个最小生成树 T

MST-PRIM(G, w, r):
1.  for each u in V:
2.      key[u] = ∞
3.      π[u] = NIL
4.  key[r] = 0
5.  Q = V
6.  while Q is not empty:
7.      u = EXTRACT-MIN(Q)  // 从 Q 中取出 key 最小的节点 u
8.      for each v in Adj[u]:
9.          if v in Q and w(u,v) < key[v]:
10.             π[v] = u
11.             key[v] = w(u,v)
12.             DECREASE-KEY(Q, v, key[v])  // 更新 Q 中节点 v 的 key 值
13. T = {(π[v], v) | v ∈ V - {r}}
14. return T

其中，`key[u]` 表示节点 u 到当前生成树的距离，`π[u]` 表示节点 u 在当前生成树中的父节点，`EXTRACT-MIN(Q)` 表示从集合 Q 中取出 `key[u]` 最小的节点 u，并将其从 Q 中删除，`Adj[u]` 表示节点 u 的邻居节点集合，`w(u,v)` 表示边 (u,v) 的权重，`DECREASE-KEY(Q, v, key[v])` 表示将集合 Q 中节点 v 的 `key[v]` 值更新为新值 `key[v]`。