Union-Find or DFS: which one is better to find a connected component?

Union-Find and DFS can be used to search for connections. Which one is better in what condition?

+4
source share
2 answers

The join-search algorithm is best suited for situations where the equivalence relation changes, i.e. there are Union operations that must be performed on your partition set. Given a fixed undirected graph, you don’t have any equivalence relations at all - the edges are all fixed. OTOH, if you have a graph with the addition of new edges, DFS will not crop it. While DFS is asymptotically faster than find-union, in practice, the probable deciding factor will be the actual problem you are trying to solve.

tl; dr - Static graph? DFS! Dynamic graph? Union-find!

+10
source

, DFS (O (n) O (n alpha (n)), alpha (n) Ackermann), - find , , (, ).

+7

All Articles