Union-Find或DFS:哪一个更适合查找连接组件？

Question

Union-Find和DFS都可以用于查找连接性。在哪种情况下哪种更好？

Answer 1

联合查找算法最适合于等价关系发生变化的情况，即存在需要在一组分区上执行的“联合”操作。给定一个固定的无向图，等价关系根本不会改变--边都是固定的。OTOH，如果你有一个添加了新边的图，DFS不会剪切它。虽然DFS比union-find渐近地快，但在实践中，可能的决定因素是您试图解决的实际问题。

tl;dr -静态图？DFS！动态图？联合-发现！

Answer 2

如果图已经以邻接列表格式存在于内存中，那么DFS稍微更简单和更快( O(n )与O(n alpha(n))，其中alpha(n)是逆Ackermann)，但是联合查找可以处理以任何顺序在线到达的边，这有时是有用的(例如，有太多的边不适合主内存)。

Answer 3

如果图已经以邻接表或矩阵的形式给出，那么DFS/BFS更合适，但是如果给定边/关系列表，那么它更适合使用dsu (不相交集)，就好像你要从边制作图，然后先制作图，然后再画dfs，但是通过形成dsu，你可以直接计算组件的数量和每个组件中的节点/边的数量。