Depth-first vs Breadth-first [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 8 years ago.

Improve this question

With my experience, it seems that DFS is much more popular than BFS. For example, DFS is more memory efficient. But I just wanna know when BFS will outweigh DFS? In what certain case, we should prefer choose BFS rather than DFS?

Answer 1

The advantage of BFS is that it goes by levels, so if you have reason to believe whatever your looking for is in the top nodes BFS is probably better. If your sure it's on the bottoms, DFS might be better since it doesn't take any particular levels first.

The example I remember reading is when looking for medical records, you're more likely to need newer medical records than older ones, which are probably on the bottom on the tree.

Answer 2

For arbitrary graphs there is no such way to prove that which one is better as in some case DFS is more efficient on others BFS is efficient. But for trees you can certainly prefer one over other. For example You are traversing binary tree then , the stack space required by the DFS is O(logN) whereas by BFS it is O(N) for queue. But if you are using a sparse graph then BFS might use less space then DFS. The time complexity on average is same for both but you might find DFS preferable if solution is present at higher depth from root or BFS if it is closer to the root