c++ - 最快的最小生成树算法

Question

http://en.wikipedia.org/wiki/Minimum_spanning_tree

我希望将我的最小生成树算法与最佳中的最佳算法进行基准测试。有人知道我在哪里可以找到这些算法的 C++ 实现吗？我用谷歌搜索并没有找到任何东西。如果这些算法是最好的，那么肯定在某个地方一定有 C++ 实现吗？

迄今为止最快的最小生成树算法是由 David Karger、Philip Klein 和 Robert Tarjan 开发的，他们发现了一种基于 Borůvka 算法和反向删除算法组合的线性时间随机算法。[2][3] Bernard Chazelle 提出的最快的非随机算法基于软堆，一个近似优先级队列。[4][5] 它的运行时间为 O(m α(m,n))，其中 m 是边数，n 是顶点数，α 是 Ackermann 函数的经典反函数。函数 α 增长非常缓慢，因此对于所有实际目的，它可以被认为是一个不大于 4 的常数；因此 Chazelle 的算法需要非常接近线性时间。如果边缘权重是具有有界位长度的整数，然后确定性算法具有线性运行时间。 [6] 对于一般权重是否存在具有线性运行时间的确定性算法仍然是一个悬而未决的问题。然而，Seth Petie 和 Vijaya Ramachandran 发现了一种可证明的最优确定性最小生成树算法，其计算复杂度未知。 [7]

我已经针对 Boost C++ 的图形算法进行了测试。

Answer 1

当维基百科页面说“最快的最小生成树算法”时，他们的意思是具有最低渐近边界的算法——在这种情况下，O(m α(m,n))，定义了 m、n 和 α就像你粘贴的报价一样。简而言之，这意味着对于非常大的输入值，所花费的时间将始终以 C*m*α(m,n) 为界，对于某些 C 值。但请注意，C 可能非常大——即，当应用于较小的输入值时，此算法可能比其他算法慢，即使对于非常大的输入值它比其他算法更快。

在比较两种算法的渐近界时，没有“测试”来查看哪个更快——您只需证明每种算法的渐近界，然后看看哪个更低。（“渐近”是指输入大小变为无穷大时的行为——并且很难使用无限大小的输入值运行测试。）

但请注意，在某些情况下您不应该使用渐近最快的算法。如果“C”非常大，那么您最好使用更简单的算法来处理较小的数据值。

我的猜测是您的算法可能会在 C 上有所改进，但不会在渐近界上有所改进。但是，如果我错了，那么您应该将其提交给 ACM！

有关详细信息，请参阅：http ://en.wikipedia.org/wiki/Big_O_notation

Answer 2

“关于排序、堆和最小生成树”，Gonzalo Navarro 和 Rodrigo Paredes

介绍了一些“最佳中的最佳”内核和外部存储器测量，并提供了对旧实现的参考。

他们将 I/O 数量和 CPU 时间报告为图形大小的函数，并很好地描述了他们的测试用例，因此原则上您可以进行测试并与他们发布的图表进行比较。您可以使用他们的 Prim2 参考（来自 Peter Sanders 的代码，他免费提供了许多快速代码）来校准您自己的测量值。