如何使用Fibonacci堆实现Prim的算法？

Question

我知道Prim的算法,我知道它的实现,但我总是跳过一个我想问的部分.有人写道,Prim与Fibonacci堆的算法实现是O(E + V log(V)),我的问题是:

• 什么是斐波纳契堆？
• 它是如何实现的？和
• 如何用Fibonacci堆实现Prim的算法？

Answer 1

Fibonacci堆是一个相当复杂的优先级队列,在其所有操作上具有出色的amoritzed渐近行为 - inserted,find-min和reduce-key都在O(1)摊销时间运行,而delete和extract-min在摊销的O中运行(lg n)时间.如果您想要对该主题有一个很好的参考,我强烈建议您阅读CLRS的"算法入门,第2版"并阅读其中的章节.它写得非常好,非常具有说明性. Fredman和Tarjan的斐波纳契堆原始论文可在线获取,您可能需要查看.它很密集,但对材料进行了很好的处理.

如果你想看到Fibonacci堆和Prim算法的实现,我必须为我自己的实现提供一个无耻的插件:

1. 我实现了Fibonacci堆.
2. 我使用Fibonacci堆实现Prim的算法.

这两个实现中的注释应该很好地描述它们的工作方式; 让我知道我能做些什么来澄清!

Answer 2

Prim的算法选择在已经选择的涡旋组和其余涡旋之间具有最低权重的边缘.
因此,要实现Prim算法,您需要一个最小堆.每次选择边缘时,都会将新涡旋添加到已经选择的涡旋组中,并且其所有相邻边缘都会进入堆中.
然后从堆中再次选择具有最小值的边.

所以我们得到的时间是:
Fibonacci:
选择最小边= 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最小选择(它最后是一棵树).

所以在Min堆中你会得到:

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

在Fibonacci堆你会得到:

O(Vlog(V)+ E)