1

我一直在学习 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] = 无穷大！但是该图显示了 (c) 部分的不同步骤！

啊啊啊！为什么？

4

2 回答 2

4

MO 的一个人很友好地通过电子邮件回答。问题是我没有注意到通过 ExtractMin(Q) 操作一次添加一个树节点。

以下是他给的回复：

*您的分析实际上是完全正确的，但是您（和我）对更新 key[v] 和 pi(v) 的含义感到困惑。特别是，当您更新 pi(v) 时，您不会将其添加到树中。仅当从 Q 中提取节点 u 时，才会将节点 u 添加到树中（沿着将其连接到其父 pi(u) 的边）。所以一切都像您描述的那样进行，但在它结束时，您只完成了步骤(a)，而不是步骤 (c)。这是该程序在这种情况下所做的事情的简要说明：

  • （第 1-3 行）所有节点都放在 Q 中（不在树中的节点集），它们的父节点被声明为 NIL，并且它们的键（即沿单条边到现有树的最小距离）设置为无穷
  • （第4行）根节点（节点a）的key设置为0
  • （第 6 行）从 Q 中删除具有最小键的节点 u（即根节点 a）并添加到树中
  • （第 8-11 行）节点 b 和 h 的键更新为 4 和 8，并且将 pi(b) 和 pi(h) 设置为 u（但 b 和 h没有从 Q 中提取）。这样就完成了步骤 (a)
  • （第 6 行）从 Q 中删除具有最小键的节点 u（现在是节点 b，键 = 4）并通过其父节点（即 pi(b)=a）添加到树中
  • （第 8-11 行）节点 c 的 key 更新为 8，pi(c) 设置为 b。由于 key(h)=8 小于 11=w(b,h)，所以不更新 h 的 key 和 parent。这样就完成了步骤 (b)
  • （第 6 行）从 Q 中删除具有最小键的节点 u（节点 c，键 = 8，但也可能是节点 h，键 = 8）并通过其父节点（即pi(c)=b)
  • （第 8-11 行）更新节点 d、i 和 f 的键和父节点，完成步骤 (c)
  • ETC。*
于 2009-12-20T05:09:23.870 回答
0

您的描述是正确的，算法确实设置了 key[h] = 8 正如您在步骤 a 中描述的那样。

步骤 c 有一个关键关系，您可以根据需要选择 h，但示例选择 c。

查看它的最佳方法是查看每个步骤的优先级队列中的（非无限）元素（就在 ExtractMin 之前）：

1: Q = (a, 0)           - removes a, sets key[b]=4, key[h]=8
2: Q = (b, 4), (h, 8)   - removes b, sets key[c]=8
3: Q = (h, 8), (c, 8)   - could pick either h or c, they have the same key
于 2009-12-20T00:42:04.067 回答