Prim aLgorithm的快速实现

Question

我使用的是Prim算法的geeksforgeek C++ implementation，但我在一些测试用例中遇到了超过时间限制的问题。那么有没有更快的实现呢？这是我目前正在使用的实现。为了让问题变得通用，在C++中Prim Algo的最快实现是什么？

Answer 1

Prim的这种实现效率非常低。在每次迭代中，它寻找最小的边，在所有边上进行迭代。例如，如果您使用binary heap，您将拥有一个渐近更快的实现(对于您当前的实现，m*log(n)与m*n )。此外，你应该编写自己的代码，而不是使用别人已经为你编写的代码。