查找周期：DFS 与联合查找？

Question

带有着色的 DFS 将采用O(V+E)vs union find 将作为O(ElogV) 参考：http : //www.geeksforgeeks.org/detect-cycle-undirected-graph/

所以 union find 方法比较慢。如果 V = 100、E = 100、DFS = 200，则联合发现为 1,000。是否有理由使用联合查找？我个人喜欢它，因为它产生了一个干净的代码。或者我错过了什么工会发现在实际实践中更好？

Answer 1

我怀疑您可能误解了大 O 表示法的工作原理。符号 O(V + E) 并不意味着“运行时间是通过将 V 和 E 相加来计算的），而是“运行时间作为 V 和 E 之和的函数进行缩放。”例如，假设您运行 DFS在具有 1,000 个节点和 1,000 条边且运行时间为 1 毫秒的图上。假设具有 2,000 个节点和 2,000 条边的图上的运行时间类似于 2 毫秒是合理的。但是，大 O 符号本身不会如果您没有建立一些参考点，告诉您某些给定输入上的运行时将是什么。我在这里给出的 1ms 数字是一个完全的猜测 - 您必须运行实现以查看您获得的运行时。

类似地，运行时间 O(E log V) 表示“运行时间缩放为节点数和边数的对数的乘积。）例如，如果具有 1,000 个节点和 1,000 个边的输入的运行时间为 1ms ，那么具有 1,000 个节点和 2,000 条边的输入的运行时间可能为 2 毫秒，而具有 1,000,000 个节点和 1,000 条边的输入的运行时间同样约为 2 毫秒。再次，找出运行时间的唯一方法一些初始输入是运行它，看看会发生什么。

另一个细节 - 正如许多其他人所指出的，联合查找数据结构上给出的界限是针对一个非常低效的联合查找结构。使用具有路径压缩和按秩并集的不相交集森林，您可以获得每次操作的渐近运行时间 O(α(n))，其中 α(n) 是一个增长极其缓慢的函数（阿克曼逆函数）对于可以放入宇宙的所有输入，这基本上是 5。

话虽如此 - DFS 的渐近运行时间比联合查找方法更好，因此它在实践中可能是更快的。DFS 也相对容易实现，所以我建议采用这种方法。

union-find 结构的优势在于，它适用于不断添加边的连接问题的增量版本。DFS 不能很好地处理这种情况。

Answer 2

具有路径压缩和按秩并集的联合查找将具有O(E*?(n))复杂性，其中?(n)是逆阿克曼函数。它的运行时间与 DFS 相当，但就我个人而言，我会使用 DFS，这是一种更简单、更明显的完成工作的方式。

我能想到的更喜欢 union-find 的唯一原因是当我们有一些无序列表/边集作为图形表示时的情况，我们不能或不想使用额外的时间/内存来转换这些数据对于 DFS。