CODEWITHSUNDEEP
algorithmdepth-first-searchbreadth-first-search
venkysmarty
venkysmarty

Reputation: 11431

Difference between BFS and DFS

I am reading about DFS in Introduction to Algorithms by Cormen. Following is text snippet.

Unlike BFS, whose predecessor subgraph forms a tree, the predecessor subgrpah produced by DFS may be composed of several trees, because search may be repeated from multiple sources.

In addition to above notes, following is mentioned.

It may seem arbitrary that BFS is limited to only one source where as DFS may search from multiple sources. Although conceptually, BFS could proceed from mutilple sources and DFS could limited to one source, our approach reflects how the results of these searches are typically used.

My question is

  1. Can any one give an example how BFS is used with multiple source and DFS is used with single source?

Upvotes: 5

Views: 9573

Answers (2)

davin
davin

Reputation: 45525

When it says multiple sources it is referring to the start node of the search. You'll notice that the parameters of the algorithms are BFS(G, s) and DFS(G). That should already be a hint that BFS is single-source and DFS isn't, since DFS doesn't take any initial node as an argument.

The major difference between these two, as the authors point out, is that the result of BFS is always a tree, whereas DFS can be a forest (collection of trees). Meaning, that if BFS is run from a node s, then it will construct the tree only of those nodes reachable from s, but if there are other nodes in the graph, will not touch them. DFS however will continue its search through the entire graph, and construct the forest of all of these connected components. This is, as they explain, the desired result of each algorithm in most use-cases.

As the authors mentioned there is nothing stopping slight modifications to make DFS single source. In fact this change is easy. We simply accept another parameter s, and in the routine DFS (not DFS_VISIT) instead of lines 5-7 iterating through all nodes in the graph, we simply execute DFS_VISIT(s).

Similarly, changing BFS is possible to make it run with multiple sources. I found an implementation online: http://algs4.cs.princeton.edu/41undirected/BreadthFirstPaths.java.html although that is slightly different to another possible implementation, which creates separate trees automatically. Meaning, that algorithm looks like this BFS(G, S) (where S is a collection of nodes) whereas you can implement BFS(G) and make separate trees automatically. It's a slight modification to the queueing and I'll leave it as an exercise.

As the authors point out, the reason these aren't done is that the main use of each algorithm lends to them being useful as they are. Although well done for thinking about this, it is an important point that should be understood.

Upvotes: 8

DarthVader
DarthVader

Reputation: 55032

Did you understand the definition? Did you see some pictures on the holy book?

When it says that DFS may be composed of several trees it is because, it goes deeper until it reaches to a leaf and then back tracks. So essentially imagine a tree, first you search the left sub tree and then right subtree. left sub tree may contain several sub trees. that s why.

When you think about BFS, it s based on level. level first search in other words. so you have a single source (node) than you search all the sub nodes of that level.

DFS with single source if there is only one child node, so you have only 1 source. i think it would be more clear if you take the source as parent node.

Upvotes: 0

Related Questions