无法理解prims算法

Question

请帮助理解prims，所有伪码(如在核心和维基) 普里姆算法。

​

    MST-PRIM (G, w, r) {
for each u ∈ G.V
u.key = ∞
u.parent = NIL
r.key = 0
Q = G.V
while (Q ≠ ø)
//1
u = Extract-Min(Q)
for each v ∈ G.Adj[u]
if (v ∈ Q) and w(u,v) < v.key
v.parent = u
v.key = w(u,v)}

​

我能理解到直到1或同时循环，r.key=0保证首先扫描根的近邻或邻接，但由于u已经属于Q (到目前为止还不包括在素数最小生成树中的节点队列)和v(也在q中)，将无助于生成素数MST。

同时，coreman和wiki都表示

​

 1. A = { (v, v.parent) : v ∈ V - {r} - Q }.
2. The vertices already placed into the minimum spanning tree are those in V−Q.
3. For all vertices v ∈ Q, if v.parent ≠ NIL, then v.key < ∞ and v.key is the weight of a light edge 

​

在第6-11行的while循环的每一次迭代之前，(v，v.parent)将v：：连接到已经放置在最小生成树中的某个顶点。

既然A是我们的MST，那么，既然v已经包含在我们的MST中(如v∈V- {r} -q所示)，那么为什么会有帮助呢？

Answer 1

对于你有疑问的部分：

u = Extract-Min(Q) 
for each v ∈ G.Adj[u]
if (v ∈ Q) and w(u,v) < v.key
v.parent = u
v.key = w(u,v)

“对于每个顶点v，属性v:key是连接到树中顶点的任何边的最小权重；按照约定，如果没有这样的边，key =∞。”(∞)

因此，u =Extract(Q)将得到具有最小键的顶点。

对每个v G.Adju都会找到u的所有邻居。

if (v∈Q)和w(u，v) < v.key条件，以消除循环并检查路径是否应该更新。

然后，下面的代码行更新邻居的边缘。

v.parent = u
v.key = w(u,v)

“在行6-11，1.a={ (v，v.parent)：v∈V- {r} -q }的每次迭代之前”(算法)

基于上述语句，在while循环A为空之前，Q= G.V！在while循环之后，您将得到A包含构成MST的所有顶点。A中的每个顶点v都有一个父(v.parent)。对于根r，它的父级为零。根r由于语句V- {r}而被排除在外，但由于其以v.parent形式出现的子元素，它在A中存在。

因此，在这个链接算法中，它指出："2.已经放置在最小生成树中的顶点是V−Q中的顶点。“

“当算法终止时，最小优先级队列Q为空；G的最小生成树A因此为A={ (v，v.parent)：v∈V- {r}”。