如何用斐波那契堆实现Prim算法？
我知道Prim的算法，也知道它的实现，但是我总是跳过现在要问的一部分。它被写了普里姆与算法的实现斐波那契堆是O(E
+ V log(V))和
- 简而言之，斐波那契堆是什么？
- 如何实施？和
- 如何用Fibonacci堆实现Prim’s算法？
回答：
Fibonacci堆是一个相当复杂的优先级队列，在所有操作上都有出色的渐近行为-插入，查找-最小和减小键全部在O（1）摊销时间内运行，而删除和提取-
最小在摊销O中运行（lg
n）时间。如果您想在这个主题上有很好的参考，我强烈建议您拿起CLRS的“算法简介，第二版”的副本，并阅读其中的章节。它写得很好并且非常说明性。
弗雷德曼（Fredman）和塔里安（Tarjan）撰写的有关斐波那契堆的原始论文可在线获得，您可能想看看。它很稠密，但是可以很好地处理材料。
如果您想看到Fibonacci堆的实现和Prim的算法，我必须为自己的实现提供一个无耻的插件：
- 我的斐波那契堆的实现。
- 我使用Fibonacci堆实现Prim算法的实现。
这两个实现中的注释都应该很好地描述它们如何工作。让我知道我是否可以做任何澄清的事情！
以上是 如何用斐波那契堆实现Prim算法？ 的全部内容， 来源链接： utcz.com/qa/418340.html
