20

我知道Prim 的算法，也知道它的实现，但我总是跳过我现在想问的部分。有人写道，Prim 的斐波那契堆算法实现是O(E + V log(V))，我的问题是：

  • 简而言之，斐波那契堆是什么？
  • 它是如何实施的？和
  • 如何用斐波那契堆实现 Prim 算法？
4

3 回答 3

32

斐波那契堆是一个相当复杂的优先级队列，它的所有操作都具有出色的摊销渐近行为 - 插入、查找最小值和减少键都在 O(1) 摊销时间内运行，而删除和提取分钟在摊销 O 中运行(lg n) 时间。如果您想对该主题有很好的参考，我强烈建议您阅读 CLRS 的“算法简介，第 2 版”并阅读相关章节。它写得非常好，而且非常具有说明性。 Fredman 和 Tarjan 关于斐波那契堆的原始论文可在线获取，您可能想查看一下。它很致密，但对材料进行了很好的处理。

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

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

这两个实现中的注释应该很好地描述了它们的工作原理；让我知道是否有什么我可以做的澄清！

于 2011-01-28T08:13:39.617 回答
12

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)

于 2011-01-28T07:56:23.737 回答
2

几年前我使用斐波那契堆实现了 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 算法，那么使用 Fibonacci 堆并没有真正的困难 - 只需像往常一样使用堆的insert和deletemin方法，并使用reducekey方法来更新顶点当您释放通向它的边缘时。

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

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

I have a report and a presentation I wrote after doing that, that explain a bit how to proceed (for Dijkstra - see the end of the ppt for the Fibonacci heap functions in pseudo-code) but it's all in French... and my code is in Caml (and French) so I'm not sure if that helps!!! And if you can understand something of it please be indulgent, I was just starting programming so my coding skills were pretty poor at the time...

于 2011-01-28T08:46:06.183 回答