带着色的 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，Union find 为 1,000。 有理由使用 Union find 吗？我个人喜欢它，因为它产生了干净的代码。 或者我错过了工会发现在实际实践中更好的任何事情？
最佳答案
我怀疑您可能误解了大 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 个节点的输入上边是 1 毫秒，那么具有 1,000 个节点和 2,000 条边的输入的运行时间可能是 2 毫秒，而具有 1,000,000 个节点和 1,000 条边的输入的运行时间同样约为 2 毫秒。同样，找出运行时间的唯一方法将根据一些初始输入运行它，看看会发生什么。
另一个细节——正如许多其他人所指出的，联合查找数据结构上给出的界限是针对一个非常低效的联合查找结构。使用具有路径压缩和按等级并集的不相交集合森林，您可以获得每个操作的 O(α(n)) 的渐近运行时间，其中 α(n) 是一个增长极其缓慢的函数(阿克曼反函数)对于您可以放入宇宙中的所有输入，这基本上是 5。
话虽如此 - DFS 的渐近运行时比 union-find 方法要好，因此它在实践中可能更快。 DFS 也相对容易实现，因此我建议采用这种方法。
union-find 结构的优势在于它适用于连续添加边的连接问题的增量版本。DFS 不能很好地处理这种情况。
关于algorithm - 查找周期 : DFS versus union-find?，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45272145/