When should you use one over the other?

If you just have to visit each node once without memory constraints (e.g., number of islands problem), then it doesn't really matter which one you use. It comes down to your personal preference for recursion/stack vs queue.

BFS is better at:

DFS is better at:

  • uses less memory than BFS for wide graphs (that is, graphs with large breadth factors), since BFS has to keep all the nodes in the queue, and for wide graphs, this can be quite large.
  • finding nodes far away from the root, e.g., looking for an exit in a maze.

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.