如何使用min-heap实现Prim算法？

Question

是否也可以使用fibonacci堆实现Prim算法？欢迎任何形式的帮助。

Answer 1

任何类型的最小堆都可以用于Prim的算法。然而，请注意，尽管Fibonacci堆在某些操作上比二进制堆具有更好的渐近复杂性，但我已经经验证明，由于常量很大，它只有在真正大的图(数十亿甚至数百亿条边)时才优于二进制堆。