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!
source
share