4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What does "all practically conceivable applications" mean? CLRS is presumably talking about asymptotic worst-case performance, so it sounds like you're comparing apples with oranges. $\endgroup$ – David Richerby Sep 27 '15 at 8:56
  • $\begingroup$ @DavidRicherby $α(2^{2^{2^{2^16}}}) \approx 4 $ so… it’s practically a small constant. $\endgroup$ – Rishav Sep 27 '15 at 11:13
2
$\begingroup$

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))$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I’m talking about the static case here, Union Find seems to be faster as well. $\endgroup$ – Rishav Sep 27 '15 at 12:49
  • $\begingroup$ Union-find has an extra multiplicative factor $\alpha(V)$, which makes it slower than DFS asymptotically (and probably practically as well). $\endgroup$ – Yuval Filmus Sep 27 '15 at 12:50
  • $\begingroup$ I think that DFS is asymptotically faster, but slower for all practical applications, because as I said, α of 2^2^2^2^16 (which is a huge number), is about 4. When the authors of CLRS call DFS faster, they probably mean so asymptotically and hence my confusion. Does this reasoning sound about right? $\endgroup$ – Rishav Sep 27 '15 at 12:55
  • $\begingroup$ I don't see why you think that union-find is faster. In practice I would bet that DFS is faster. The only way to know is to program both and compare running times. $\endgroup$ – Yuval Filmus Sep 27 '15 at 12:56
  • $\begingroup$ I think I shall try that. Thanks for your advice! $\endgroup$ – Rishav Sep 27 '15 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.