最快的最小生成树算法

Question

最快的最小生成树算法

12

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

我希望能够将我的最小生成树算法与最佳算法进行比较。有人知道我可以在哪里找到这些算法的C++实现吗？我已经使用Bing和Google搜索了，但没有找到任何信息。如果这些算法是最好的，肯定会有C++实现的，对吧？

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

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

- toto

2个回答

3

《关于排序、堆和最小生成树》 Gonzalo Navarro 和 Rodrigo Paredes

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

他们将I/O次数和CPU时间作为图形大小的函数进行报告，并对其测试用例进行了详细描述，因此你可以进行测试并与他们发布的图表进行比较。你可以使用他们的Prim2参考（Peter Sanders编写的代码，他会免费提供许多快速代码）来校准自己的测量结果。

- Erik Kruus

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Edward Loper · Accepted Answer

当维基百科页面提到“最快的最小生成树算法”时，它们指的是渐进界最低的算法--在本例中为O(m α(m,n))，其中m、n和α的定义如您所引用的引语。简单来说，这意味着对于非常大的输入值，所花费的时间将始终受到C*m*α(m,n)的限制，其中C的值为某个值。但请注意，C可能非常大--即使在较小的输入值上应用此算法可能比其他算法更慢，尽管在非常大的输入值上更快。

当比较两个算法的渐近界时，并没有“测试”来确定哪个更快--您只需证明每个算法的渐近界，并查看哪个更低。（“渐近”是指随着输入大小趋向于无穷大时的行为--使用无限大小的输入值进行测试很困难。）

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

我猜测您的算法可以改善C，但不会改善渐近界。但如果我在这一点上错了，那么您应该将其提交给ACM！

有关更多信息，请参见：http://en.wikipedia.org/wiki/Big_O_notation