Prim 的最小生成树算法 - 算法中的混乱
我一直在研究 Cormen 等人的书，我对他们提供的算法有点困惑。我已经通过维基百科了解了 Prim 算法的概念是如何工作的，但我无法使用我书中提供的算法来模仿它的工作原理。
请参阅该章节的在线副本： http://www. cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/minimumSpanningTrees.pdf
算法在上述链接的第 13 页上给出，示例图在前一页上。
现在，使用示例案例中的算法，第一步：
u <--- 节点 A 到 ExtractMin(Q)。 然后如图所示，Adj[u] 中有两个条目：节点 b 和节点 h。
现在首先设置v<----节点b。然后检查 v 是否属于 Q。确实如此。检查 w(u,v) 是否 <键[v]。真的。所以 PI[v] <--- u 和 key[v] <--- w(u, v)。 我就这么多了这显示在第 12 页图表的 (b) 中。
但是算法说“对于 Adj[u] 中的每个 v”。
所以下一步应该设置v<---节点h。 然后检查 v 是否属于 Q。确实如此！并且 w(u,v) <键[v]？这是！因为 key[v] = 无穷大！ 但该图显示了 (c) 部分中的不同步骤！
啊啊啊！为什么？
I've been studying from the Cormen et al book and I'm a bit confused regarding the algorithm they have provided. I've understood how the concept of Prim's algo works through wikipedia, but I can't mimic that working using the algorithm provided in my book.
Refer to this online copy of the chapter:
http://www.cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/minimumSpanningTrees.pdf
The algo is given on page 13 in the above link and an example diagram is on the previous page.
Now, using the algorithm on the example case, in the first step:
u <--- node A through ExtractMin(Q).
Then there are two entries in Adj[u] as per the diagram: node b and node h.
Now first set v <---- node b. Then check if v belongs to Q. It does. Check if w(u,v) < key[v]. True. So PI[v] <--- u and key[v] <--- w(u, v).
I got this much. This is shown in (b) of the diagram on pg 12.
BUT the algo says "for each v in Adj[u]".
So the next step should set v <--- node h.
Then check if v belongs to Q. It does! And is w(u,v) < key[v]? It is! Since key[v] = infinity!
But the diagram shows a different step in part (c)!
Aaaaaah! Why?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
MO 的一位工作人员很友善地通过电子邮件回复了我。
问题是我没有注意到树节点是通过 ExtractMin(Q) 操作一次添加一个的。
以下是他给出的答复：
*你的分析其实是完全正确的，但是你（和我）
对更新 key[v] 和 pi(v) 的含义感到困惑。在
特别是，当您更新 pi(v) 时，您不会将其添加到树中。一个
节点 u 被添加到树中（沿着将其连接到其节点的边）
父 pi(u)) 仅当它从 Q 中提取时才有效。所以一切都会继续进行
就像你所描述的，但最后，你只完成了步骤
(a)，而不是步骤(c)。这是该程序在其中执行的操作的概要
情况：（
树），它们的父母被声明为 NIL，并且它们的密钥（即
沿单边到现有树的最小距离）设置为
无穷大
从 Q 中删除并添加到树中
pi(b) 和 pi(h) 设置为 u（但 b 和 h 不是从 Q 中提取的）。
这就完成了步骤 (a)
key=4) 从 Q 中删除并通过其父级添加到树中（其中
pi(b)=a)
b.由于 key(h)=8 小于 11=w(b,h)，因此 h 的键和父级
没有更新。这样就完成了步骤 (b)
也可能是节点 h（也有 key=8）从 Q 中删除
并通过其父节点添加到树中（即 pi(c)=b）
One of the guys at MO was kind enough to answer by email.
The problem was that I didn't notice that the tree nodes are added one at a time via the ExtractMin(Q) operation.
Here is the reply he gave:
*Your analysis is actually completely correct, but you (and I)
were confused about what updating key[v] and pi(v) means. In
particular, when you update pi(v), you do not add it to the tree. A
node u is added to the tree (along the edge connecting it to its
parent pi(u)) only when it is extracted from Q. So everything proceeds
like you described, but at the end of it, you've only completed step
(a), not step (c). Here's a run-down of what the program does in that
case:
tree), their parents are declared to be NIL, and their key (i.e.
minimum distance to the existing tree along a single edge) is set to
infinity
removed from Q and added to the tree
pi(b) and pi(h) are set to u (but b and h are not extracted from Q).
This completes step (a)
key=4) is removed from Q and added to the tree via its parent (which
is pi(b)=a)
b. Since key(h)=8 is smaller than 11=w(b,h), the key and parent of h
are not updated. This completes step (b)
could also have been node h, which also has key=8) is removed from Q
and added to the tree via its parent (which is pi(c)=b)
您的描述是正确的，算法确实设置了 key[h] = 8，如您在步骤 a 中所述。
步骤 c 有一个关键的联系，如果需要，您可以选择 h，但该示例选择了 c。
查看它的最佳方法是查看每一步的优先级队列中有哪些（非无限）元素（就在 ExtractMin 之前）：
Your description is correct, the algorithm does set key[h] = 8 as you describe in step a.
Step c has a key tie, you could pick h if you want, but the example picks c instead.
The best way to see it is to see what (non-infinite) elements are in the priority queue at each step (just before the ExtractMin):