The Memory Problem with BFS
Reading 2 ended with an uncomfortable fact about breadth-first search: it has to hold every node at every level of the search tree in memory before it can move to the next level. For small problems this is manageable. For large ones it is not. A real navigation graph with millions of intersections, or a game with billions of possible positions, would exhaust available memory long before BFS found a solution.
The root cause of this memory problem is the way BFS explores. It insists on finishing every node at one level before touching any node at the next. That means it must simultaneously remember the entire frontier — every node at the current edge of exploration — at all times. As the search goes deeper, the frontier grows exponentially and memory runs out.
Depth-first search (DFS) takes a completely different approach. Instead of spreading out in all directions simultaneously, it picks one path and follows it as far as it will go. It commits. It does not keep track of every unexplored alternative at every level. It goes deep, and only backs up when it has to.
How Depth-First Search Works
The idea behind DFS is captured well in the way most people actually explore a physical maze. You pick a direction and walk. You keep walking until you either reach the exit or hit a dead end. If you hit a dead end, you do not teleport back to the entrance and try every other corridor in order — you backtrack to the most recent junction where you had an unexplored option, and try that one instead. You are always following one thread through the maze, not trying to spread your attention across the whole map at once.
DFS works the same way. The procedure is:
- Start at the start state.
- Pick one available transition and follow it to the next state.
- From that new state, pick one available transition and follow it again.
- Keep going deeper until either the goal state is found, or a dead end is reached (a state with no unexplored transitions).
- When a dead end is reached, backtrack to the most recent state that still has unexplored transitions, and try one of those instead.
- Continue until the goal is found or all reachable states have been visited.
The key to DFS's memory efficiency is step 5. When DFS backtracks, it can discard everything it learned about the dead-end path — those states no longer need to be remembered. At any given moment, DFS only needs to keep track of the single path it is currently following, plus the record of unexplored alternatives at each junction along that path. That is a much smaller memory footprint than BFS, which must remember every node at every level simultaneously.
Tracing DFS Through a Maze
A maze is one of the most natural illustrations of DFS because the physical experience of solving a maze is so close to what DFS actually does. Let us trace DFS through a small example and watch the backtracking happen.
The maze below is a five-by-five grid. Each cell is either open (white) or a wall (dark). The agent starts at S in the top-left corner and needs to reach G in the bottom-right. From any open cell, the available transitions are moves up, down, left, or right into adjacent open cells. Moving into a wall is not a legal transition.
Dark = wall | White = open | S = start | G = goal
DFS begins at S and must choose a direction. The available transitions from S are: right (to row 0, col 1) and down (blocked by wall). Only one legal move exists: go right.
Step 1 — S moves right to (0,1)
From (0,1), the agent can go left back to S (already visited — skip it), or down to (1,1). DFS picks down.
Step 2 — (0,1) moves down to (1,1)
This is the first real junction. From (1,1) the agent can go:
- Up, back to (0,1) — already visited, skip
- Down, to (2,1) — open
- Right, to (1,3) is blocked by the wall at (1,2) — not available directly
The only forward option is down. DFS goes down to (2,1). This junction is recorded: if the downward path fails, DFS will return here.
Step 3 — (1,1) moves down to (2,1)
From (2,1), options are: up to (1,1) (visited), or right to (2,2). DFS goes right.
Step 4 — (2,1) moves right to (2,2)
From (2,2), options are: left to (2,1) (visited), or right to (2,3). DFS goes right.
Step 5 — (2,2) moves right to (2,3)
From (2,3), the agent can go: left to (2,2) (visited), up to (1,3), or down to (3,3). Two new options! DFS picks one — say, up.
Step 6 — (2,3) moves up to (1,3)
From (1,3), the only options are down to (2,3) (visited). This is a dead end. DFS backtracks.
After Step 6: agent is at (2,3) having backed up from the dead end at (1,3) marked ✗
Step 7 — Back at (2,3), now try down to (3,3)
DFS backtracks from (1,3) to (2,3) and tries the other unexplored option: down. From (3,3), the only new option is down to (4,3).
Step 8 — (3,3) moves down to (4,3)
From (4,3), the agent can move right to (4,4). That is the goal cell — G is found.
Solution: S → (0,1) → (1,1) → (2,1) → (2,2) → (2,3) → (3,3) → (4,3) → G
8 moves. One dead end visited and abandoned. DFS found the solution by following one path at a time, backing up exactly once when it hit a dead end.
Notice what DFS did not do. When it was at (1,1) and chose to go down, it did not also immediately expand (0,1) again or check whether other paths from the start were worth exploring first. It committed to the downward path and followed it. That commitment is what keeps memory use low: DFS only needs to remember the current path and the junctions it has not yet backtracked to.
Why BFS Would Be Strange in a Maze
It is worth pausing to appreciate why BFS feels so unnatural in a maze context, even though it is perfectly correct. BFS would explore the maze like this:
Start at S. The only neighbor is (0,1). Move there (Level 1 complete). Now expand (0,1): its neighbor is (1,1). Move there (Level 2 complete). Now expand (1,1): its neighbor is (2,1). But wait — BFS rules say we must expand all Level 2 nodes before any Level 3 nodes. (1,1) is the only Level 2 node, so this actually works fine here. But in a maze with more branches, BFS would require the agent to teleport back to the entrance to explore a parallel corridor before continuing down the current one.
Imagine this more vividly: you are in a maze and you reach a junction. You go left and walk ten steps to another junction. BFS would require you to stop, walk all the way back to the entrance, find every other path that branches off at Level 1, walk to the end of each, then walk all the way back to the junction ten steps in, then continue. No sensible person would search a maze this way. DFS is the natural strategy for physical exploration precisely because you cannot be in two places at once — you have to commit to one path at a time.
For AI agents that operate in physical or simulated spaces, DFS often matches the structure of the problem much better than BFS. The maze is not just a convenient example; it reveals something true about when DFS is the right tool.
An Important Limitation of the Maze Example
The maze is a good illustration of DFS behavior, but it hides one of DFS's most important properties: a maze has exactly one solution (if it is solvable at all). There is only one path from S to G. DFS will find it eventually no matter what choices it makes at junctions, because the solution is the only path that does not dead-end. DFS cannot find a bad solution in a maze — it can only find the solution, or fail to find it at all.
Real AI problems are rarely like this. Most have multiple paths to the goal, with very different costs. And this is where DFS can go seriously wrong.
When DFS Goes Wrong: The Road Trip Example
Return to our Cedar Falls to Chicago navigation problem. Chicago is to the east. A human glancing at a map immediately understands that heading east is promising and heading west is not. DFS does not have that understanding unless someone builds it in. DFS just picks a direction and follows it.
Suppose DFS, starting from Cedar Falls, happens to pick the transition toward Des Moines first. Des Moines is southwest — the wrong direction entirely. But DFS does not know that. It arrives in Des Moines and finds new transitions: maybe it can continue to Omaha. It goes to Omaha. From Omaha, maybe it goes to Kansas City. From Kansas City, maybe St. Louis. From St. Louis, Memphis.
DFS is now hundreds of miles south of where it started, heading in completely the wrong direction. And it will keep going. It will not stop and reconsider until it hits a dead end or, by some circuitous path, eventually reaches Chicago from the south. It might find Chicago — but via a route that adds thousands of miles and dozens of unnecessary stops to the journey.
This is not a failure to follow the algorithm correctly. DFS did exactly what it is supposed to do: pick a path and follow it deep. The problem is that DFS has no mechanism for evaluating whether a path is heading in a useful direction. It treats Cedar Falls → Des Moines → Omaha as just as reasonable a starting move as Cedar Falls → Waterloo, because both are legal transitions. Without additional information to distinguish them, DFS cannot prefer one over the other.
This is a deeper issue than just "DFS made a bad first choice." Even if DFS started well and went to Waterloo, it might then pick Independence over Cedar Rapids for a good reason — or for no reason at all. At every junction, it chooses without knowing which direction leads toward the goal. In a small graph with few junctions, this does not matter much. In a large graph with many choices, DFS can wander badly before finding a solution.
DFS in the Analysts and Hackers puzzle: When you worked through that puzzle, you probably did something closer to DFS than BFS. You picked a sequence of moves and followed it for several steps, then backed up when you got stuck. Most students go about six or seven moves deep before feeling like they have run out of good options and starting over from near the beginning. That is backtracking — the heart of DFS — even if you were not thinking of it that way.
Depth Limits
A note on a practical fix — not on the assessment. One of DFS's worst failure modes is when the state graph contains cycles or very long paths that lead nowhere useful. An agent that goes Cedar Falls → Des Moines → Omaha → Kansas City → … might keep going indefinitely without ever reaching Chicago. In practice, implementations of DFS often impose a depth limit: a maximum number of transitions the agent is allowed to follow before it must backtrack. If the solution is not found within the depth limit, the agent gives up on that path and tries another. Depth limits trade off completeness (the agent might miss a solution that requires more than the limit allows) for practicality (the agent will not run forever). This is one of many refinements to basic DFS that computer scientists have developed over decades — a reminder that the algorithms we cover here are foundations, not endpoints.
BFS and DFS Side by Side
Having now seen both algorithms in action, it is worth summarizing their tradeoffs clearly. Neither is universally better — they make different choices about what to prioritize.
| Property | Breadth-First Search | Depth-First Search |
|---|---|---|
| Exploration order | Level by level — all nodes at depth N before any at depth N+1 | One deep path at a time — commit until dead end, then backtrack |
| Memory use | High — must hold entire frontier at all times | Low — only the current path and unexplored junctions |
| Finds shortest path? | Yes, guaranteed (when cost is uniform) | Not guaranteed — may find a long or roundabout solution first |
| Will always find a solution? | Yes, if one exists and the graph is finite | Not if paths are infinite or cycles exist (without depth limit) |
| Uses domain knowledge? | No — treats all transitions as equally worth exploring | No — treats all transitions as equally worth exploring |
| Best for | Small, well-defined problems where shortest path matters | Large state spaces where memory is limited and any solution will do |
The last row in the comparison table is telling: both BFS and DFS treat all transitions as equally worth exploring. Neither one knows anything about whether a particular direction is likely to lead toward the goal. BFS does not know that Waterloo is the right first step from Cedar Falls; it explores Dike, Hudson, and Waverly too. DFS does not know that heading toward Des Moines is a mistake; it might follow that path for hundreds of miles before reconsidering.
This shared limitation — no sense of direction, no ability to prioritize — is what motivates the approach in Reading 4. If we could give the search algorithm some knowledge about which transitions are likely to be useful, we could avoid the wasted exploration that makes both BFS and DFS inefficient on large problems. That knowledge has a name: a heuristic.