Data structures and patterns · Question 40 of 50
BFS or DFS?
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 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.