4
$\begingroup$

In finding the connected components in a graph, why do we use DFS, instead of BFS?

$\endgroup$
  • $\begingroup$ stackoverflow.com/questions/2869647/… $\endgroup$ – Eugene Apr 8 '17 at 21:47
  • $\begingroup$ Can you edit the question to clarify exactly how you were thinking to use BFS to find connected components? That would provide us a more concrete basis for comparison. Finding connected components is not just "use DFS and read off the answer"; there's some subtlety involved. $\endgroup$ – D.W. Apr 9 '17 at 16:40
4
$\begingroup$

Two components $G_1(V_1, E_1)$ and $G_2(V_2, E_2)$ are connected if and only if there is a path between any vertex $v_1\in V_1$ and any other vertex $v_2\in V_2$. Here I'm assuming that both components are known to be connected, i.e., there is a path between any pair of vertices $v_i, v_j$ in any component (so that finding a path between any pair of vertices between both components fully connects them).

Hence, in finding connected components the procedure consists of starting in any vertex of $G_1$ and collecting all nodes that are reachable from it. Clearly, this can be done either with depth-first search or breadth-first search:

  1. Breadth-first search visits nodes in order of their depth from the start state, $s$. This way, it finds all paths of length 1, then length 2 and so on. Its main advantages are: it guarantees it will eventually find a solution (given sufficient memory, see below) and that the solution found is optimal; also, it can avoid transposition by maintaining a CLOSED list that stores all nodes previously expanded. Its main disadvantage is that it takes an exponential amount of memory (unless the graph being traversed is known to be polynomial but this is a rare case indeed).

  2. Detph-first search generates paths of arbitrary length until a goal is found or a threshold is reached. Its main advantage is that it takes memory which is linear in the depth of the search tree developed. Its main disadvantage is that it cannot guarantee that it will ever find a solution and, if it does, that the solution is optimal.

Now, considering the problem stated above it becomes clear that the goal is not to reach a specific goal but to collect nodes reachable from the goal state. For this, there is no specific need to be optimal so that the question reduces to whether the available memory might be enough or not: whereas Breadth-First search does not provide any guarantee, Depth-First search does.

That is why we use Depth-First Search Mostly because: one, there is no need to find an optimal solution; second, memory matters!

Cheers,

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ BFS takes an exponential amount of memory? Exponential in what? The memory used by BFS is at most linear in the number of vertices in the graph. $\endgroup$ – D.W. Apr 9 '17 at 16:39
  • $\begingroup$ In the depth of the search tree generated: While Breadth-First Search takes $O(bˆd)$, Depth-First Search takes $O(d)$ ---with $b$ being the branching factor and $d$ the depth. By the way, it is not customary to use BFS for Breadth-First Search (even if the context helps) as it usually means "Best-First Search" which is an entirely different category of search algorithms. $\endgroup$ – Carlos Linares López Apr 10 '17 at 7:55

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.