基于堆或排序的Kruskal算法

Question

我正在尝试尽可能高效地实现Kruskal算法。

为了提高运行效率，使用堆或排序算法对边进行排序是否有区别？

除此之外，还有哪些技术可以使Kruskal算法更加高效？

- XerXes

---

这是那种只有一个正确答案的问题：使用自己的数据对所有选项进行基准测试，没有通用答案。在某些图形的平均情况下，使用堆可能具有优势，但堆在缓存方面非常糟糕。如果你试图“尽可能高效”，我想你不希望缓存未命中拖慢你的代码速度。 - Juan Lopes

Answer 1

这取决于您要解决的确切问题。如果您正在实现通用解决方案，只需选择“最快”的排序算法。我怀疑这不是堆排序。我会使用Java默认的排序算法（如果您正在排序对象，则可能是timsort）。此外，在某些情况下，排序可以比O（ElogE）更快地完成。比如说，您的边只能有整数权重，并且在一个小区间内，那么也许您可以选择与countsort非常相似的东西。因此，如果您处于这种情况中，堆远非一个好选择。此外，我看不出为什么在Kruskal算法的上下文中单独使用堆。 回答您的第二个问题（但您可能已经知道了），并查集数据结构的使用可以提高速度，用于集合操作。它具有各种优点：易于实现，良好的渐近行为和低常数。 编辑 我重新考虑了堆/堆排序选项，主要是由于我的帖子上的评论。如果只在树被完全排序之前使用堆，那么使用堆确实可能带来巨大的优势。我的看法已经变了180度。原因如下。

考虑Erdős–Rényi model。现在，这是一个非常简单的模型，在这个模型中，我们从一个有n个顶点（即没有边）的空图G开始，并以概率p将每个可能的边添加到G中，与任何其他边都无关。当组成树时，这并不完全是Kruskal算法所做的，但如果G具有二次数量的边（以顶点数为基础），边分布不“偏向”和权重分配不“偏向”，它与之相似。

现在进入有趣的部分。在Erdős-Rényi模型下，当p约为ln(n)/n时（即在图中添加O(nln(n))条边后），图形成连接（大致如此）。这个结果已经为一段时间所知（请检查here）。

尽管如此，对于Kruskal算法，如果G具有与顶点数量成二次的边数，边分布不“偏倚”，权重分配也不“偏斜”，则有可能在O(nln(n))条边内到达树。如果确实如此，那么使用堆并仅在完成树之前进行排序比在开始组成树之前使用比较排序方法对整个边集进行排序更好。

因此，使用堆可能会加快运行时速度，并且可能是相当可观的。

- cobarzan

---

我认为使用堆的主要好处是能够进行部分排序，只需对树进行完整排序即可。如果在您的数据集中，树通常可以在O（V）边内到达，则使用堆可以加快速度。但是，堆具有非常高的常数，因此必须实现显著的加速才值得麻烦。 - Juan Lopes

重新思考，堆排序的另一个好处是更好的最坏情况复杂度。对于有严格时间限制的实时系统，能够确定地预测算法需要多长时间（无论输入如何）是一种优势。 - Juan Lopes

我用堆和排序算法实现了Kruskal算法，事实上，对于那些实例，堆的速度更快。但是今天我再次测试，现在它们的速度都一样。我真的无法理解这个。 - XerXes

我进行了更多的研究，并遇到了这个网址：http://www.dcc.uchile.cl/~gnavarro/ps/algor09.pdf。 - cobarzan