0

请帮助理解 prims 算法伪代码（在 coreman 和 wiki 中） Prim's algorithm。

    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 或 while 循环 r.key=0 确保首先扫描根的邻居或相邻节点，但由于 u 已经属于 Q（节点队列直到现在不包括在 prims 最小生成树中）和 v同样在 Q 中，将无助于生成 prims MST。

也是 coreman 和维基状态

 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，那么 1. 将如何提供帮助，因为 v 已经包含在我们的 MST 中（如 v ∈ V - {r} - Q 所示）为什么应该包含它。

4

1 回答 1

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 = ∞。” （http://en.wikipedia.org/wiki/Prim's_algorithm）

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

对于每个 v ∈ G.Adj[u]将找到 u 的所有邻居。

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

然后以下代码行更新邻居边。

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

“在第 6-11 行的 while 循环的每次迭代之前，1. A = { (v, v.parent) : v ∈ V - {r} - Q }。”（http://en.wikipedia.org /wiki/Prim's_algorithm )

根据上面的说法，在while循环之前A是空的，因为Q = GV！在 while 循环之后，您将得到 A 包含形成 MST 的所有顶点。A 中的每个顶点 v 都有一个父节点（v.parent）。对于根 r，其父级为 NIL。由于陈述 V - {r}，根 r 被排除在外，但由于其子代以 v.parent 的形式存在，它存在于 A 中。

因此，在此链接http://en.wikipedia.org/wiki/Prim's_algorithm中，它指出：“2. 已经放置到最小生成树中的顶点是 V-Q 中的顶点。”

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

于 2014-11-08T19:29:13.277 回答