Data structures and patterns · Question 40 of 50

BFS or DFS?

What they're checking

Choosing the right graph traversal.

The answer

Both visit every node and edge once: O(V + E). BFS uses a queue and explores level by level, so the first time it reaches a node, it is by the fewest edges: shortest paths in unweighted graphs, "the minimum number of steps", the nearest of something. DFS uses a stack or recursion and goes deep first: finding cycles, topological order (course schedules, build order), connected components, every path, backtracking.

Mark nodes as visited, or cycles loop forever. Very deep recursion can overflow the stack, so switch to an explicit stack. For weighted shortest paths use Dijkstra, with a priority queue, not BFS.

The picture

        A
      /   \
     B     C
    / \     \
   D   E     F
BFS: A B C D E F   level by level (queue)
DFS: A B D E C F   deep first (stack)
The follow-up they'll ask

The shortest path through a grid with walls?

Show the answer

BFS from the start; each cell's neighbours are the four directions that are not walls; the step count when you reach the end is the answer.

Your progress stays on this device.