why is dfs treated differently

[johndoe444]

hi,
in cormen's book while traversing bfs we are given a source node from which we start traversing. but for dfs we do the traversal for each node iteratively. why is this done so? i mean the difference between both traversals should be on the way it is done (the order of traversing nodes) and the goal should be the same ie reaching all nodes.

Moreover, it says for dfs we get forest while for dfs we get tree. but this is kind of strange because for the same graph if we traverse bfs for each node we get also different trees which have different roots ie forests. If the configuration is the same we get the same thing.

[abhimanipal]

The objective of BFS is to print all the nodes at a given level, then move to the next level

In DFS we go depth wise as far as we can go. Then when we cant go any further we backtrack and then try again and so on.

DFS gives you a forest because you have many connected components as opposed to BFS where you have only 1 connected component. (Read the definition of connectivity for better understanding of this)

[johndoe444]

I was reading the book again and I have some idea why he presented it like this. Correct me if I am wrong. Later in the book he discussed many other applications using dfs like topological sorting and strongly connected component. For this reason we want the particular version of the dfs to conduct dfs on each vertex on the graph. To verify this, for normal traversal we don't need finishing time. But it has a field named so to deal with the application demands. And bfs are not required in the same way as bfs. Hence I guess when the graph traversal from a given source is required we can use either bfs and dfs. And we get tree because only one root (source vertex) is given. If we were required by an application to traverse the whole graph then we could use bfs as well in the same way as dfs.

[abhimanipal]

That is correct.