我知道Prim's algorithm，我知道它的实现，但是始终我跳过现在要询问的部分。据说Prim的Fibonacci heap的算法实现是O(E + V log(V))，并且我的问题是：
斐波那契堆是一个相当复杂的优先级队列，在所有操作上都具有出色的渐近行为-插入，查找-最小和减少键全部在O（1）摊销时间内运行，而删除和提取-最小运行在摊销O（lg n）时间。如果您想在这个主题上有很好的参考，我强烈建议您拿起CLRS的“算法简介，第二版”的副本，并阅读其中的章节。它写得很好并且非常说明性。 The original paper on Fibonacci heaps by Fredman and Tarjan可以在线获得，您可能想检查一下。它很致密，但可以很好地处理材料。
[如果您想看到Fibonacci堆的实现和Prim的算法，我必须为我自己的实现提供一个无耻的插件：
这两个实现中的注释都应该很好地描述它们如何工作；让我知道我是否可以做任何澄清！
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）
几年前，我使用斐波那契堆实现了Dijkstra，问题非常相似。基本上，斐波那契堆的优点在于，它使查找集合的最小值成为常数操作；因此这对于Prim和Dijkstra非常合适，在每个步骤中您都必须执行此操作。
为什么很好
[使用二项式堆的算法（这是更“标准的”方式）的复杂度为O（E * log V），因为-大致-您将尝试每个边（E），对于每个边，您将将新顶点添加到二项式堆（对数V）或减小其键（对数V），然后必须找到堆的最小值（另一个对数V）。
相反，当您使用斐波那契堆时，在堆中插入顶点或减小其键的成本是恒定的，因此您只有一个O（E）。但是删除一个顶点是O（log V），因此，由于最后每个顶点都将被删除，从而增加一个O（V * log V），因此总共O（E + V * log V）。
因此，如果您的图足够密集（例如E >> V），则使用斐波那契堆比使用二项式堆更好。
如何
因此，想法是使用Fibonacci堆来存储可从您已经构建的子树访问的所有顶点，并根据通往该顶点的最小边的权重来索引。如果您了解使用其他数据结构的实现或Prim的算法，那么使用Fibonacci堆并没有真正的困难-只需像通常那样使用堆的insert和deletemin方法，并且释放通往顶点的边时，请使用decreasekey方法更新顶点。
唯一困难的部分是实现实际的斐波那契堆。
我无法在此处提供所有实现细节（需要花费页面），但是当我完成时，我非常依赖Introduction to algorithms (Cormen et al)。如果您还没有，但是对算法感兴趣，我强烈建议您得到它的副本！它与语言无关，它提供了有关所有标准算法及其证明的详细解释，并且肯定会提高您的知识和使用所有标准算法，设计和证明新算法的能力。 This PDF（来自您链接的Wikipedia页面）提供了一些实现细节，但绝对不如算法简介。]]清晰。
我有一个report和一个presentation，我在写完之后写了一点，这解释了如何继续（对于Dijkstra-请参见伪代码中的Fibonacci堆函数的ppt末尾），但这全都在法语...而我的code用的是Caml（和法语），所以我不确定是否有帮助！！！而且，如果您能理解其中的某些内容，请放心，我刚刚开始编程，因此当时的编码技能还很差...