BFS vs DFS: when does it actually matter which one you use?
I can implement both, but I get stuck deciding which one a problem wants. My current rule of thumb:
- BFS when I care about the fewest edges (shortest path in an unweighted graph), or want to explore "layer by layer."
- DFS when I need to fully explore one branch before backing up, like detecting cycles or checking whether something is reachable at all.
Is that the right way to think about it? Are there cases where either works and it's just preference?
Comments
For plain reachability either works, and it really is preference. I usually pick DFS because recursion is shorter to write.
Your rule of thumb is solid. One more: BFS uses more memory on wide graphs, DFS on very deep ones.