文件名称：optimal-mst:Pettie和Ramachandran描述的最佳MST算法
文件大小：371KB
文件格式：ZIP
更新时间：2024-05-22 23:57:39
java graph-algorithms data-structures mst Java
最优化 在2002年，Seth Pettie和Vijaya Ramachandran描述了基于决策树复杂性的。 我们没有找到算法的实际实现，因此这可能是第一个。 注意事项 尽管此算法具有最佳渐近运行时间，但对于任何实际应用而言，当然都不是最佳算法。 老实说，这整个项目仅具有相当的学术目的。 唯一感兴趣的部分可能是我们其他mst算法的实现（出于测试目的，我们实现了由prim，kruskal，boruvka和fredman / tarjan设计的mst算法）以及斐波那契堆和软堆的实现。 有关最佳mst算法的实现的其他说明 在当前的实现中，决策树的深度是有界的。 实际上，该算法永远不要使用深度大于16的树。 有关更多信息，请参阅我们的