Take a graph $G=(V,E)$ .

As we know both DFS and BFS are graph search algorithms .

But why the algorithm for BFS is designed in such a way that it does not cares about the vertices that are not connected to the source vertex $s$ but DFS takes care about all vertices in $V$.

I mean if $G$ has $l$ connected components and a vertex $s$ is in one of the connected component among $l$ , then if $s$ is the source vertex for BFS , then BFS performs only traversal on the only one connected component (which contains $s$).

If $G$ is input for BFS , it constructs one BFS tree (for component which contains $s$).

But in case of DFS , it constructs a DFS forest with $l$ DFS trees.

Why no BFS forest and it is restricted to a specifc component (containing $s$)? Any reason involved ?

For Bfs algorithm page # 595 and for Dfs algorithm page # 604 from here

  • 1
    $\begingroup$ Could you please explain how DFS is able to jump from a connected component that contains s to another connected component that does not contain s? $\endgroup$ – wookie919 Aug 16 '14 at 6:58
  • $\begingroup$ @wookie919 because for every vertex in the graph which is not visited DFS calls DFS_visit on that vertex . So, it covers all vertices in a graph . $\endgroup$ – hanugm Aug 16 '14 at 7:00
  • 4
    $\begingroup$ What's preventing you from doing the same with BFS? I think you may have mis-understood the difference between BFS and DFS. There is no mechanism in DFS (in its purest form) to allow it to reach a vertex that can't be reached from the source, unless you modify it so that it can. $\endgroup$ – wookie919 Aug 16 '14 at 7:06
  • $\begingroup$ @wookie919 Purest form of DFS means ? Is it when DFS is applied on a connected graph ? $\endgroup$ – hanugm Aug 16 '14 at 7:09
  • 3
    $\begingroup$ @wookie919 is right; this is an arbitrary design decision for implementation that has nothing to do whatsoever with the different algorithmic ideas. Also, I'm pretty sure we covered this before but I can't find the older question. $\endgroup$ – Raphael Aug 16 '14 at 9:38

Both BFS and DFS are algorithms for exploring a single connected component, and there are also several others. All such algorithms can be extended to explore all connected components in a graph.

  • 1
    $\begingroup$ (sorry to post a comment here; this post has been closed.) @hanu CLRS (Section 22.3) gives an (official) explanation for this: Although conceptually, BFS could proceed from multiple sources and DFS could be limited to one source, our approach reflects how the results of these searches are typically used. BFS is usually employed to find shortest-path distances (and the associated predecessor subgraph) from a given source. DFS is often a subroutine in another algorithm (,as we shall see later in this chapter). $\endgroup$ – hengxin Nov 14 '14 at 6:36

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