1

In a undergraduate level class I'm taking the instructor was introducing us to searching algorithms specifically Breadth First Search and Depth First Search. Now he was teaching us about how BFS was complete (that it finds the goal in every situation) while DFS wasn't complete.

Now the argument he gave supporting this was that if in a tree we run BFS and a branch is infinity long and the goal is on another branch DFS will never complete. Now the problem I have is that one can make the same argument for BFS i.e. a node has an infinite amount of neighbours and the goal is one of the descendent of the neighbours. This will result in BFS never finding the goal state.

So can one give me a better example to show that BFS is complete while DFS is not.

S. Salman
  • 590
  • 1
  • 6
  • 22
  • [Completeness of depth-first search](http://stackoverflow.com/questions/9250630/completeness-of-depth-first-search) check this post. – YoungHobbit Sep 13 '15 at 18:53
  • 1
    I believe there was an assumption made that each node can have only finite number of children. – Piotr Jaszkowski Sep 13 '15 at 19:16
  • 1
    If you do not assume limited number of children then in fact it is not complete. Assume that root has infinite number of children, and the first child has a single child with desired property. BFS will get stuck in investigating children of the root. That is assuming it will somehow enqueue all children of the root :) – Piotr Jaszkowski Sep 13 '15 at 19:27
  • Further to what @PiotrJaszkowski is saying: BFS is strictly "better" than DFS in this sense, because every graph that causes BFS to get stuck (namely, graphs with a node with an infinite number of neighbours) will also cause DFS to get stuck (DFS will never backtrack "up" from such a node) -- but not every graph that causes DFS to get stuck will cause BFS to get stuck. – j_random_hacker Sep 14 '15 at 12:40

0 Answers0