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

The union-find algorithm is best suited for situations where the equivalence relationship is changing, i.e., there are “Union” operations which need to be performed on your set of partitions. Given a fixed undirected graph, you don’t have the equivalence relationships changing at all – the edges are all fixed. OTOH, if you have a graph with new edges being added, DFS won’t cut it. While DFS is asymptotically faster than union-find, in practice, the likely deciding factor would be the actual problem that you are trying to solve.

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

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)