在Kruskal的算法中使用union-find实际上会影响最坏的运行时吗？

Question

所以我正在教自己一些图算法，现在在Kruskal上，并且了解到推荐使用union-find，所以检查添加边是否只需要O(Log )时间。出于实际目的，我明白为什么您会想要这样做，但严格地使用Big表示法，这样做真的会影响最坏情况的复杂性吗？

我的推理是:如果我们没有进行联合查找，而是做了一个DFS来检查周期，那么它的运行时将是O(E+V)，对于O(V^2 + VE)的运行时，您必须执行V次。它比联合查找更多，这将是O(V * LogV)，但是Kruskal的大部分复杂性来自于删除优先级队列E时间的最小元素，即O(E * logE)，这是大O的答案。我也看不到空间优势，因为联合查找占用了O(V)空间，使用DFS查找循环所需维护的数据结构也是如此。

因此，对一个简单问题的解释可能过长:在Kruskal的算法中使用union-find实际上会影响最坏的运行时吗？

Answer 1

并理解建议使用union-find所以检查添加边是否只需要O(日志V)时间

这不对。使用联合发现就是O(alpha(n) * m)，其中alpha(n)是Ackermann函数的逆函数，从所有意图和目的来看，都可以被认为是常数。比对数快得多：

由于alpha(n)与此函数相反，对于所有远程实用的n值，alpha(n)都小于5。因此，每项操作的摊还运行时间实际上是一个小常数。

但是Kruskal的大部分复杂性来自删除优先级队列E次的最小元素

这也是错误的。Kruskal算法不涉及使用任何优先级队列。它涉及到从一开始就按成本对边缘进行分类。尽管复杂性仍然是您在这一步中提到的。然而，排序实际上可能比优先级队列更快(使用优先级队列充其量相当于堆排序，而堆排序不是最快的排序算法)。

底线，如果m是边数，n是节点数。

1. 排序边缘：O(m log m)。
2. 对于每个边，调用union-find：O(m * alpha(n))，或者基本上只调用O(m)。
3. 总复杂度：O(m log m + m * alpha(n))。
4. 如果你不使用联合查找，总复杂度将是O(m log m + m * (n + m))，如果我们使用您的O(n + m)循环查找算法。虽然这一步的O(n + m)可能是一个轻描淡写，因为您也必须以某种方式更新您的结构(插入一个边缘)。天真的不相交集算法实际上是O(n log n)，更糟糕的是。

注意:在本例中，如果您愿意，可以编写log n而不是log m，因为m = O(n^2)和log(n^2) = 2log n。

总结:是的，联合查找帮助很多。

即使您使用了union的O(log n)变体，这将导致O(m log m + m log n)的总体复杂性，您可以将其同化为O(m log m)，但实际上，如果可以的话，您宁愿保持第二部分的速度更快。由于union-find很容易实现，所以没有理由不这样做。