在Kruskal算法中使用并查集是否会影响最坏情况的运行时间？

Question

所以我正在学习一些图算法，现在是克鲁斯卡尔算法，了解到建议使用并查集来检查添加边是否会创建环，只需要花费O(Log V)的时间。对于实际目的，我理解为什么要这样做，但是严格按照大O符号来看，这样做实际上会影响最坏情况下的复杂度吗？

我的推理：如果我们不使用并查集，而使用DFS来检查循环，那么运行时间将为O(E+V)，您必须执行V次才能获得O(V^2 + VE)的运行时间。虽然比使用并查集的O（V * LogV）更多，但Kruskal的主要复杂性来自于从优先队列E中删除最小元素，其答案为O(E * logE)，即大O答案。我也没有看到空间优势，因为并查集需要O（V）空间，而使用DFS找到循环所需的数据结构也需要O（V）空间。

对于一个可能过于冗长的问题的简单回答：在Kruskal算法中使用并查集实际上会影响最坏情况下的运行时间吗？

- Chirayu Poudel

---

你的问题有一个主要缺陷，DFS 不仅会执行 V 次，而且可能会执行 O(E) 次，因为需要评估 E 条边。Kruskal 算法的主要复杂度在于边的排序。你可以使用优先队列来进行排序，但这不是必需的。 - Juan Lopes

啊，那正是我错了的地方。谢谢！ - Chirayu Poudel

Answer 1

并且了解使用并查集是推荐的，这样检查添加边是否创建环只需要花费O(Log 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. 如果您不使用 union-find，则总体复杂度将为 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-find 帮了很多。

即使您使用 O(log n) 变体的并查集，这将导致总复杂度为 O(m log m + m log n)，但您可以将其归纳为 O(m log m)，但在实践中，如果可能的话，您更愿意让第二部分更快。由于并查集非常易于实现，因此真的没有理由不这样做。

- IVlad

---

嗨，谢谢你的回答。我不明白为什么不能两种方式都实现，因为它们都提供了一种以 O(ElogE) 的时间访问最小元素的方法（通过删除最小元素 E 次的优先级队列，以及使用 O(ElogE) 排序来排序）。无论哪种方式，我的问题仍然存在。由于复杂度的大部分来自于一个 O(ELogE) 的东西，无论是通过优先队列还是排序，那么并查集对于最坏情况的时间复杂度是否有影响？ - Chirayu Poudel

@ChirayuPoudel 并查集与访问最小元素无关。 - Juan Lopes

@ChirayuPoudel 我已经添加了更多细节。如果您有更多问题，请告诉我。 - IVlad

只有一个小细节：由于m是O(n^2)，所以O(m log m) = O(m log n)，因为O(m log n^2) = O(2 m log n)。 - Juan Lopes