principleMinor
DFS vs. Union Find for computing connected components of a static graph
Viewed 0 times
graphuniondfscomponentsconnectedforfindstaticcomputing
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#47596, answer score: 5
Revisions (0)
No revisions yet.