DFS with coloring would take O(V+E) vs union find would take O(ElogV)
reference: http://www.geeksforgeeks.org/detect-cycle-undirected-graph/
So union find approach is slower. If V = 100, E = 100, DFS = 200, Union find is 1,000. Is there a reason to use Union find? I personally like it because it produces a clean code. Or anything I missed that union find is better in real practice?
我怀疑您可能误解了 big-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 不能很好地处理这种情况。