如何用斐波那契堆实现Prim算法？

Question

我知道 Prim 算法 并且我知道它的实现，但我总是跳过我想要的部分现在就问。据记载，Prim 的算法实现 斐波那契堆 是 O(E + V log( V)) 和我的问题是：

• 简单来说什么是斐波那契堆？
• 它是如何实施的？如何
• 使用 Fibonacci 堆实现 Prim 算法？

Answer 1

斐波那契堆是一个相当复杂的优先级队列，它的所有操作都具有出色的摊余渐近行为 - 插入、查找最小值和减少键都在 O(1) 摊余时间内运行，而删除和提取最小值在摊余 O 时间内运行(lgn) 时间。如果您想要有关该主题的良好参考，我强烈建议您购买 CLRS 出版的《算法导论，第二版》并阅读其中的章节。它写得非常好并且非常说明性。 Fredman 和 Tarjan 关于斐波那契堆的原始论文< /a> 可以在线获取，您可能想查看一下。它很致密，但可以很好地处理材料。

如果你想看看斐波那契堆和 Prim 算法的实现，我必须为我自己的实现提供一个无耻的插件：

1. 我的斐波那契堆实现。
2. 我的实现Prim 的算法使用斐波那契堆。

这两个实现中的注释应该很好地描述了它们的工作原理；如果有什么我可以澄清的，请告诉我！

Answer 2

Prim 的算法在已选择的顶点组和其余顶点之间选择权重最低的边。
所以要实现Prim的算法，你需要一个最小堆。每次选择一条边时，都会将新顶点添加到已选择的顶点组中，并且其所有相邻边都会进入堆中。
然后再次从堆中选择具有最小值的边。

所以我们得到的时间复杂度是：
斐波那契：
选择最小边 = O(去除最小值的时间) = O(log(E)) = O(log(V))
将边插入堆 = O(将项插入堆的时间) = 1

最小堆：
选择最小边 = O(从堆中移除最小值的时间) = O(log(E)) = O(log(V))
向堆插入边 = O(向堆插入项的时间) = O(log(E)) = O(log(V))

（记住 E =~ V^2 ... 所以log(E) == log(V^2) == 2Log(V) = O(log(V))

，总共有 E 个插入和 V 个最小选择（最终是一棵树）。

因此 最小堆你会得到：

O(Vlog(V) + Elog(V)) == O(Elog(V))

在斐波那契堆中你会得到：

O(Vlog (V) + E)

Answer 3

几年前我使用斐波那契堆实现了 Dijkstra，问题非常相似。基本上，斐波那契堆的优点在于它使查找集合的最小值成为一个常数操作；所以这对于 Prim 和 Dijkstra 来说非常合适，在每一步你都必须执行这个操作。

为什么它好

使用二项式堆（这是更“标准”的方式）的这些算法的复杂性是 O(E * log V)，因为 - 粗略地 - 你将尝试每条边 (E) ，对于每个顶点，您要么将新顶点添加到二项式堆 (log V) 中，要么减少其键 (log V)，然后必须找到堆的最小值（另一个 log V）。

相反，当您使用斐波那契堆时，在堆中插入顶点或减少其键的成本是恒定的，因此您只有 O(E)。但删除一个顶点的时间复杂度为 O(log V)，因此最终每个顶点都会被删除，从而增加 O(V * log V)，总共为 O(E + V * log V)。

因此，如果您的图形足够密集（例如 E >> V），那么使用斐波那契堆比二项式堆更好。

如何

因此，我们的想法是使用斐波那契堆来存储可从您已构建的子树访问的所有顶点，并按通向该子树的最小边的权重进行索引。如果您了解使用其他数据结构的实现或 Prim 算法，那么使用斐波那契堆并没有真正的困难 - 只需使用堆的 insert 和 deletemin 方法像平常一样，并在释放通向顶点的边时使用 decreasekey 方法来更新顶点。

唯一困难的部分是实现实际的斐波那契堆。

我无法在这里向您提供所有实现细节（这将需要几页），但是当我这样做时，我严重依赖 算法简介（Cormen 等人）。如果您还没有它但对算法感兴趣，我强烈建议您获取它的副本！它与语言无关，它提供了有关所有标准算法及其证明的详细解释，并且肯定会提高您使用所有这些算法以及设计和证明新算法的知识和能力。 此 PDF（来自您链接的维基百科页面）提供了一些实现细节，但绝对不如算法简介那么清晰。

我有一份报告和一份演示文稿 我在这样做之后写道，解释了一些如何继续（对于 Dijkstra - 请参阅 ppt 末尾的斐波那契堆函数以伪代码表示），但都是法语...以及我的 代码< /a> 是 Caml（和法语），所以我不确定这是否有帮助！如果你能理解其中的一些内容，请宽容，我刚刚开始编程，所以当时我的编码技能非常差......