BFS and DFS on graphs
How do you explore everything reachable exactly once?
Thirty-seven accounts, four million lines
A fraud team flags one account in a chargeback scam and wants everything linked to it: every account that shares a phone, a device or a bank account with it, then the accounts linked to those, and so on until nothing new turns up.
The first version of the script treats the links as if they formed a tree: it fetches the flagged account's links and calls itself on each linked account. Twenty minutes later the script is still running and its log has 4 million lines. When you search the log, the same 37 account ids appear again and again.
Account 1 shares a device with account 2, 2 shares a phone with 3, and 3 shares a bank account with 1. The walk goes round that ring for ever, and on every lap it branches off into the other accounts again. In a tree there is exactly one path to each node, so following every link visits each node once. These 37 accounts have many paths between them, and loops, so a walk that does not remember where it has been visits an account once for every path that leads to it. With eight links per account there are about a billion different walks of ten links, and the script is listing all of them.
The fix is to record each account the walk has already found, and never queue a recorded account again. The question is at what moment to record it.
Pause and predict At what moment should the walk mark an account as found, so that no account is ever queued twice?
Discover each node once
A graph is nodes joined by edges. In most interview problems the graph is not given directly but is hidden in something else: a grid, where each cell is joined to its four neighbours, or words joined when they differ by one letter. An explicit graph usually comes as an adjacency list.
A tree has one path to every node, so recursion on children reaches each node once. A graph has cycles and many paths. A search that does not remember which nodes it has seen either walks around a cycle forever, as the fraud script did, or reaches the same node again by every route that leads there.
So the search keeps two things. It puts a mark on every node it has discovered, meaning found for the first time. And it keeps a frontier: a stack or a queue holding the marked nodes it has not expanded yet, where expanding a node means looking at each of its neighbours.
Nothing in that argument depends on the order in which nodes leave the frontier. A stack gives DFS, a queue gives BFS, and both reach everything. A flood fill is this same search, run on a grid from one starting cell.
Mark when you enqueue
Pause and predict A BFS on an open 300 x 300 grid pushes 90,000 cells when it marks on enqueue. Mark on dequeue instead, skipping cells already marked. How many pushes?
BFS layers give the fewest steps
Pause and predict Every edge costs the same. BFS first discovers a node at distance 5. Can a later discovery of it be shorter?
DFS does not visit nodes in order of distance. It often reaches a node by a long route first, and because that node is then marked, DFS never comes back to record a shorter route.
Many sources: start from all of them at once
"Rot spreads from every rotten orange" sounds as if it needs one BFS per rotten orange. One BFS is enough if it starts with all of them in the queue at distance 0. That is a multi-source BFS. It behaves like an ordinary BFS from one imaginary extra node joined to every rotten orange, so in one O(m · n) run every cell gets its distance to the nearest rotten orange.
Big grids: no recursion
A recursive flood fill on a solid 300 x 300 block goes 90,000 calls deep, one per cell, because each call's first neighbour is unvisited. Python's default limit is 1,000 nested calls, and the in-browser Java runtime allows only a few thousand. Use an explicit stack or a queue instead: the invariant is the same, and the call stack is not involved.
A web crawler is this search over the whole web: a frontier of URLs and a set of URLs already seen, checked before a URL is queued.
How to recognise it
The pattern fits when things are connected to other things and you must reach everything that is connected, count the separate groups, or find the fewest steps from one place to another. The wording of the question then tells you which kind of search to use.
Pause and predict You need the fewest moves for a chess knight to reach a given square. Should you use DFS or BFS?
Four that only look like it
- When edges have different costs, BFS gives wrong answers: it counts edges, and a route with fewer edges can cost more. That needs Dijkstra, in shortest paths.
- When edges keep arriving and after each one you must answer "are these two connected yet?", searching again every time is too slow. That needs union-find.
- When you need an order that respects dependencies, such as courses that must come after their prerequisites, that is topological sort, which builds on this unit.
- When the input is a tree, there is only one path to each node, so no marks are needed and plain recursion works. That is in trees.
Where it bites
Pause and predict On a Java ArrayDeque: q.push(a); q.push(b); then q.poll(). Which comes out?
- Marking on dequeue. With a skip for cells already marked it still gives the right answer, but the queue fills with copies. Without the skip, the work grows exponentially.
- Recursive flood fill on a big grid. On a solid block of land the recursion goes one call deeper for every cell and overflows the call stack. Use an explicit stack or a queue.
- Using DFS for the fewest steps. DFS finds some path, not necessarily the shortest. Only BFS is guaranteed to reach each node first by a shortest path.
- Running one BFS per source. Put every source into one queue at distance 0 and run a single BFS.
- Searching outward from every cell to find which cells can reach the edge. Search once, inward from the edge cells.
- Forgetting the unreachable case. In Rotting Oranges and Word Ladder, part of the input may be impossible to reach, and the problem asks for a special answer when it is. Check for that before you return.
- Starting from one node when the graph is in pieces. The bipartite check and the island count must start a search from every node that has not been visited yet.