DFS vs. Union Find for computing connected components of a static graph

Question

According to CLRS,

When the edges of the graph are static—not changing over time—we can compute the connected components faster by using depth-first search.

However, I tried to do some runtime analysis, and in a graph $G(V, E)$ on which we have to answer $Q$ connectivity queries.

DFS would take $O(V+E)$ asymptotic time to calculate the connected components, followed by $O(1)$ to answer each query, which leads to a total running time of $O(V+E+Q)$.

Whereas, an optimised Union Find would take $O(E.α(V))$ time to “add” all the edges, followed by $O(α(V))$ per query, which gives a total running time of $O(α(V).(E+Q))$.

Now, as we, know $α$ can be taken to be a constant factor for all practically conceivable applications, so Union Find works out to be faster, hence I am confused as to why the authors of CLRS call DFS faster.

Am I making a mistake with my analysis somewhere?

Answer 1

Your running time analysis of Union-Find is incorrect. To use Union-Find for this situation, we need to perform $V$ MakeSet operations, $E$ Union operations, and $2Q$ Find operations. Each operation takes $O(\alpha(V))$ amortized time. Therefore, the total running time for the Union-Find-based algorithm will be $O(\alpha(V) (V+E+Q))$ ... not $O(\alpha(V) (E+Q))$ as you claimed. I suspect you forgot the cost of the MakeSet operations.

It seems clear that $O(\alpha(V) (V+E+Q))$ is asymptotically slower than $O(V+E+Q)$, or at least no faster.

If you care, you can reduce the running time of DFS to $O(E+Q)$ and the running time of the Union-Find algorithm to $O(\alpha(V) (E+Q))$. Basically, you first scan the graph to remove all isolated vertices (vertices with no edges incident on them). You know that the isolated vertices aren't connected to anything, so they can be ignored. Then, run your algorithm on the resulting graph, after removal of isolated vertices. For the resulting graph, we have $E/2 \le V \le E$, so $V = \Theta(Q)$ and $O(V+E+Q) = O(E+Q)$ and $O(\alpha(V) (V+E+Q)) = O(\alpha(V) (E+Q))$.

Answer 2

When the graph is dynamic, union-find can update the list of connected components in time $O(\alpha(V))$ per vertex or edge, whereas it is not clear how to run DFS progressively. So we can complement the statement you quote by

When the edges of the graph are dynamic – changing over time – DFS is not a good choice since it cannot be applied progressively; we can compute the connected components faster by using union-find.

That said, union-find is helpful only if edges and vertices are never deleted.