我一直在学习 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) < key[v]。真的。所以 PI[v] <--- u 和 key[v] <--- w(u, v)。 我得到了这么多。这显示在第 12 页图表的 (b) 中。
但是算法说“对于 Adj[u] 中的每个 v”。
所以下一步应该设置v <---节点h。 然后检查 v 是否属于 Q。确实如此!是 w(u,v) < key[v] 吗？这是!因为 key[v] = infinity! 但该图在 (c) 部分显示了不同的步骤!
啊啊啊!为什么？
最佳答案
MO 的一位员工很友好地通过电子邮件回复了我。 问题是我没有注意到通过 ExtractMin(Q) 操作一次添加一个树节点。
这是他给出的回复:
*你的分析其实是完全正确的，但是你(和我) 对更新 key[v] 和 pi(v) 的含义感到困惑。在 特别是，当您更新 pi(v) 时，您不会将它添加到树中。 A 节点 u 被添加到树中(沿着连接它的边 parent pi(u)) 只有当它是从 Q 中提取出来的时候。所以一切都会进行 就像你描述的那样，但最后，你只完成了一步 (a)，而不是步骤 (c)。这是该程序在其中执行的操作的简要说明 案例:
- (第 1-3 行)所有节点都放在 Q 中(不在 Q 中的节点集合 树)，他们的 parent 被宣布为 NIL，他们的 key (即 沿单个边到现有树的最小距离)设置为 无限
- (第4行)根节点(节点a)的key设置为0
- (第 6 行) 具有最小键的节点 u (即根节点 a) 是 从 Q 中移除并添加到树中
- (第8-11行)节点b和h的key更新为4和8，并且 pi(b) 和 pi(h) 设置为 u(但 b 和 h 不是从 Q 中提取的)。 这完成了步骤 (a)
- (第 6 行)具有最小键的节点 u(现在是节点 b，具有 key=4) 从 Q 中移除并通过其父级添加到树中( 是 pi(b)=a)
- (第8-11行)节点c的key更新为8，pi(c)设置为 b.由于key(h)=8小于11=w(b,h)，h的key和parent 没有更新。这完成了步骤 (b)
- (第 6 行) 具有最小键的节点 u (节点 c，键 = 8，但它 也可能是节点 h，它也有 key=8) 从 Q 中删除 并通过其父项(即 pi(c)=b)添加到树中
- (第 8-11 行)更新节点 d、i 和 f 的键和父节点，完成步骤 (c)
- 等等*
关于algorithm - Prim 的最小生成树算法 - 算法混淆，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1932031/