java - Kruskal 与堆或排序算法

Question

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

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

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

Answer 1

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

要回答您的第二个问题(但您可能已经知道这一点)，使用 Disjoint-set data structure 可以加快速度。对于集合的操作。它具有各种优点:易于实现、良好的渐近行为和低常数。

编辑

我已经重新考虑了堆/堆排序选项，主要是因为我帖子上的评论。如果只排序直到树完成，使用堆可能确实会带来巨大的优势。 180 度转变我的意见。这是原因。

考虑 Erdős–Rényi model .现在，这是一个非常简单的模型，其中从 n 顶点(即没有边)上的空图 G 开始，并以概率 p 添加每个可能的边 到 G，独立于任何其他边缘。这不完全是 Kruskal 算法在组成树时所做的，但如果 G 有二次方的边数(就顶点数而言)，它就“非常好”，边分布不是'biased' 并且权重分配不是'biased'。

现在有趣的部分来了。在 Erdős–Rényi 模型下，当 p 大约为 ln(n)/n 时，图变得连通(即“粗略”地说，在添加 O(nln (n)) 边到图)。结果在一段时间内众所周知(查看 here )。

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

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