最快最小生成树算法

Question

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

我期待我的基准最小生成树对最好的最好的树算法。 有人知道我在哪里可以找到这些算法的C++实现吗？我疯狂搜索并没有发现任何东西。如果这些算法是最好的，肯定肯定有一个C++实现的地方？

最快最小生成树 算法迄今被 大卫·卡尔格，菲利普·克莱恩和罗伯特 的Tarjan，谁发现基于Borůvka的算法和 反向的 组合 随机算法的线性时间内开发 - 删除算法[2] [3] Bernard Chazelle最快的非随机算法， ，基于 软堆，优先级为 队列。[4] [5]它的运行时间是O（m α（m，n）），其中m是边的数量，n是顶点的数量，并且α是阿克曼函数的经典函数逆 。函数α增长非常缓慢，因此对于所有实际目的而言，它可能被认为是不大于4的常数，不大于 。因此Chazelle的算法 需要非常接近线性时间。如果 边缘权重是具有有限位长度的整数，那么确定性算法以线性 运行时间已知。[6]如果 运行时间为0，是否存在 确定性算法与线性 一般权重的运行时间是 仍然是一个未解决的问题。然而，Seth Petie和Vijaya Ramachandran有 找到了一个可证明的最优生成树算法，其中 的计算复杂度为 未知[7]。

我已经测试了Boost C++的图算法。

Answer 1

当维基百科页面显示“最快的最小生成树算法”时，它们意味着具有最低渐近界的算法 - 在这种情况下，O（mα（m，n））与m，n ，并按照您粘贴的报价定义α。简而言之，这意味着对于非常大的输入值，对于C的某个值，所花费的时间量将总是以C * m *α（m，n）为界。但请注意，C可能非常大 - 即，当应用于较小的输入值时，这种算法可能比其他算法慢，即使它对于非常大的输入值而言比其他算法快。

当比较两种算法的渐近边界时，没有“测试”来查看哪个更快 - 只需证明每个算法的渐近边界，并查看哪个更低。 （“渐近”，是指行为作为输入大小趋于无穷大 - 而且很难运行具有无限大小的输入值测试。）

但是请注意，有这样的情况，你应该不使用渐近最快的算法。如果“C”非常大，那么对于较小的数据值，使用更简单的算法可能会更好。

我的猜测是，你的算法可能会改善C，但不是渐近的边界。但如果我错了，那么你应该把它提交给ACM！

欲了解更多信息，请参见：http://en.wikipedia.org/wiki/Big_O_notation

Answer 2

www.dcc.uchile.cl/~raparede/publ/09algorIQS.pdf “分拣，乱堆，最小生成树”， 贡萨洛纳瓦罗和罗德里戈·帕雷德斯

提供了一些“最好的”内核和外部存储器测量结果，并提供了对旧版本 实现的参考。

他们报告的I/O＃和CPU时间 图形大小的功能，并说明他们的测试用例好，所以 原则上你可以做的测试，以及与 其公布的图表进行比较。您可以使用他们的Prim2 参考（来自Peter Sanders的代码，他可以免费提供其许多快速代码的 ）来校准您自己的测量结果 。