java - 使用堆或排序算法的 Kruskal

Question

我正在尝试尽可能高效地实施 Kruskal。

对于运行时效率，使用堆或排序算法对边缘进行排序有区别吗？

还有哪些其他技术可以使 Kruskal 算法更有效地工作？

Answer 1

这取决于您要解决的确切问题。如果您正在实施通用解决方案，只需选择“最快”的排序算法。我怀疑那是堆排序。我只会使用默认情况下Java使用的任何排序算法（可能是timsort，如果你正在排序对象）。此外，在某些情况下，排序可以比O(ElogE). 假设您的边只能在一个小区间内具有整数权重，那么也许您可以选择与计数排序非常相似的东西。因此，如果您处于其中一种情况，那么堆可能不是一个好的选择。此外，我看不出有人会单独在 Kruskal 算法的上下文中使用堆的任何理由。

为了回答您的第二个问题（但您可能已经知道这一点），使用不相交集数据结构进行集合操作可以很好地加快速度。它具有各种优点：易于实现、良好的渐近行为和低常数。

编辑

我重新考虑了 heap/heapsort 选项，主要是由于我的帖子上的评论。如果只在树完成之前进行排序，使用堆可能确实会带来巨大的优势。180度转我的看法。这就是原因。

考虑Erdős-Rényi 模型。G现在，这是一个非常简单的模型，其中一个从顶点上的空图n（即没有边）开始，并将每个可能的边添加p到G，与任何其他边无关。这并不是 Kruskal 算法在组成树时所做的事情，但是如果G具有二次边数（就顶点数而言），它类似于它“非常好”，边分布没有“偏差”并且权重分配是不“有偏见”。

现在有趣的部分来了。在 Erdős-Rényi 模型下，图在p近似时变为连通的ln(n)/n（即“粗略地”说，在向O(nln(n))图添加边之后）。结果在一段时间内众所周知（请查看此处）。

尽管 Kruskal 算法的设置再次不同，但如果G具有二次边数（就顶点数而言），边分布不是“有偏差的”，权重分配也没有“有偏差”，这是合理的一棵树在O(nln(n))边缘内是可达的。如果这确实是真的，那么使用堆并且仅在树完成之前进行排序比在开始组合树之前使用比较排序方法对整个边集进行排序要好。

因此，使用堆可能也会提高运行时速度，而且可能相当可观。