When would you use BFS instead of DFS, and vice versa?

BFS (a queue) explores by distance from the start: everything one step away, then two, and so on. Use it for:

• the shortest path in an unweighted graph or grid (fewest moves),
• anything per level (level order, the minimum depth of a tree),
• multi-source spreading (the nearest exit from every cell, rotting oranges).

DFS (recursion or an explicit stack) goes as deep as possible first. Use it for:

• exploring and counting connected components (islands),
• cycle detection and topological sort (with three states in directed graphs),
• tree problems where a node combines its children’s results (height, diameter, lowest common ancestor), and backtracking.

Space: BFS holds a frontier, O(width); DFS holds a path, O(depth). A balanced tree of a million nodes is about 20 deep but 500,000 wide at the bottom, so DFS is far lighter there; a long chain is the opposite, and a recursive DFS can overflow the stack, so use an explicit stack for big or untrusted inputs.

On graphs, both need a visited set; in BFS, mark nodes when they’re added to the queue. And BFS’s shortest path only counts edges: with weights, use Dijkstra.