Kestrel Freight runs warehouses where small robots fetch shelves and bring them to packing desks. Sofia Reyes, the product manager for the warehouse robots, explains the problem.
Sofia ReyesProduct Manager
Robots waste battery on detours. For every order, I need the fewest moves from the robot to its shelf.
The warehouse floor is a grid of square cells. A robot moves one cell at a time: up, right, down or left, never diagonally. Racks fill some cells, and a robot cannot drive through a rack.
Here is a small floor, written as text. S is the robot, G is the shelf it needs, # is a rack and . is an open cell.
S..#....
.#.#.##.
.#...#..
...#...GRows count from 0 at the top and columns from 0 at the left, so the robot is at (0, 0) and the shelf is at (3, 7). Two questions come up every day on this floor:
- What is the fewest number of moves from S to G?
- Which cells can a robot reach at all? After racks move at night, some aisles may be sealed off.
Both questions are about exploring the grid cell by cell. There are two classic ways to explore, and each has its own everyday picture.
Drop a stone into still water. A ring of ripples spreads out: first every point one step from the stone, then every point two steps away, then three. The water never jumps ahead on one side.
Breadth-first search (BFS) explores a grid the same way. It visits every cell one move from S, then every cell two moves away, and so on. So when the ring reaches G, the ring's number is the fewest moves.
You explore a maze holding a ball of string, tied at the entrance. You walk down one corridor as far as you can. At a dead end, you follow the string back to the last junction that still has a corridor you have not tried, and you take that one.
Depth-first search (DFS) explores a grid the same way. It goes as deep as it can in one direction, and it backs up only when it is stuck. It reaches every corner of the maze, but the first way it finds to G may be long.
A grid is a graph#
You do not need any new structure for either search. Each open cell is a node. Its neighbours are the open cells directly up, right, down and left of it, inside the grid. Racks and the outside of the grid are not neighbours.
In this course, every search tries the neighbours in the same order: up, right, down, left. That fixed order makes every step-through repeatable, so your prediction and the player always agree.
Predict what happens
Q The robot is at (0, 0) on the floor above. How many cells are exactly one move away from it?
Answer & explanation
Answer: B
Up and left are outside the grid, and diagonal moves are not allowed. That leaves the cell to the right, (0, 1), and the cell below, (1, 0). Both are open.
2. See it move: BFS and DFS step by step#
Both searches keep a list of cells they have found but not yet handled. That list is the frontier. The whole difference between BFS and DFS is which cell leaves the frontier next.
- In BFS, the frontier is a queue. The oldest cell leaves first, like people in a line.
- In DFS, the frontier is a stack. The newest cell is handled first. With recursion, the stack is the call stack: each call waits for the deeper call to return.
BFS: rings of distance#
BFS starts with S at distance 0 in the queue. Then it repeats one step until the queue is empty. Take the cell at the front. Give each open neighbour that is not yet visited the distance plus one, and add it at the back.
In the player below, the number in each cell is its distance from S. Dashed cells are waiting in the queue, and the queue itself is listed beside the grid. Press Next to step, or Play. At a few steps the player stops and asks you to predict.
Step by step: BFS on the warehouse floor. The animated player loads in your browser.
Look at the finished picture. The numbers grow by one with every move away from S, like the ripples. G got the number 10, so the fewest moves is 10. BFS visited 21 cells to prove it, and the queue never held more than 3 cells at once.
Predict what happens
Q BFS has taken (2, 2) from the queue. Its distance is 4. Its neighbour (2, 3) is open and not yet visited. What distance does (2, 3) get?
Answer & explanation
Answer: B
A neighbour is one move further from S than the cell that found it: 4 + 1 = 5. The distance is fixed when the cell joins the queue, and it never changes after that.
DFS: deep first, then back#
DFS starts at S and marks it visited. Then it goes into the first open, unvisited neighbour, and from there into that cell's first one, and so on. When a cell has no unvisited neighbour left, DFS backtracks: it returns to the cell below it on the stack and tries that cell's next neighbour.
In this player, the number in each cell is the order DFS visited it: 1, 2, 3 and so on. The call stack is listed beside the grid, bottom first. Watch it grow as DFS dives, and shrink as it backtracks.
Step by step: DFS on the warehouse floor. The animated player loads in your browser.
DFS also reached G, but its path has 14 moves, not 10. It ran right along the top row first, because "right" comes before "down" in the neighbour order. DFS finds a path. It does not promise the shortest one.
The same open floor, both ways#
On an open floor with no racks, the difference is easy to see. Below, both searches start in the middle of a 7 by 7 floor and run until every cell is reached. This is a flood fill: marking every cell connected to the start.
Step by step: BFS floods an open floor. The animated player loads in your browser.
BFS colours the floor in diamond-shaped rings: distance 1, then 2, then 3. The queue holds one ring at a time, so it never grew past 13 cells.
Step by step: DFS floods an open floor. The animated player loads in your browser.
DFS spirals around the floor in one long walk. Every cell is on the call stack at the end of that walk, so the stack reached 49 deep: one call for every cell.
Predict what happens
Q Both searches flood the same 7 by 7 floor. Which one ends with more cells reached?
Answer & explanation
Answer: C
A flood fill reaches every cell connected to the start, whichever frontier it uses. BFS and DFS differ in the order they visit cells, not in which cells they reach.
Your turn: the visualizer#
Now draw your own floor. Pick a preset, or tap cells to add and remove racks, and move S and G. Then run BFS or DFS and step through it, forwards and back. The counter shows the cells visited, and the table under the grid compares your last BFS and DFS runs on the same floor.
Try these five, in order:
- Run BFS on the warehouse preset with Ask me to predict on. Answer each question before the player shows the step.
- Press Now try DFS on the same grid. Compare the path lengths in the table.
- Pick The long corridor. Which search visits fewer cells to reach G? Why?
- Wall G off completely, then run BFS. What does the search report when the queue runs dry?
- Turn off Stop at G and run both on An open floor. Watch the queue stay small and the stack grow tall.
The visualizer: draw a grid, then step through BFS and DFS on it. It loads in your browser.
3. Why it works: rings and dead ends#
BFS: why the first visit is the shortest#
Think about what is in the queue at any moment. S starts alone, at distance 0. When BFS takes a cell of distance d from the front, it adds cells of distance d + 1 at the back.
So the queue only ever holds cells of distance d, followed by cells of distance d + 1. It never holds three different distances at once. That means cells leave the queue in order of distance: every cell of distance 3 leaves before any cell of distance 4.
The queue holds cells at distance d, then cells at distance d + 1. So cells leave in order of distance, and BFS first reaches each cell by a shortest path.
Here is why the first visit is the shortest. Suppose BFS first reaches a cell with distance 6. A shorter path would pass through a neighbour of that cell at distance 4 or less.
That neighbour left the queue earlier, and it would have reached the cell first. So no shorter path exists.
This needs one condition: every move costs the same. If some moves cost more, for example a slow ramp, a ring no longer means "equal cost". That is the job of Dijkstra's algorithm, later in Part 3.
Predict what happens
Q Why must BFS mark a cell visited when it joins the queue, not when it leaves?
Answer & explanation
Answer: B
On an open floor, (1, 1) is a neighbour of both (0, 1) and (1, 0). If the mark waits until a cell leaves, both of them add (1, 1). On big open grids the copies multiply, and the queue fills with repeats. Mark on joining, and each cell joins once.
DFS: why it reaches everything#
DFS marks a cell when it enters it, and it only enters unmarked cells, so no cell is entered twice. It leaves a cell only after it has tried every neighbour of that cell.
So if a cell is connected to S, DFS reaches it. Follow any path from S to the cell. DFS cannot leave the first cell of that path without trying its next cell, and so on along the path.
DFS marks a cell on entry, so it enters each open cell at most once. It backtracks only after trying every neighbour, so it reaches every cell connected to the start.
What DFS does not promise is a short path. Its path to G is whatever corridor it happened to try first. On the warehouse floor that was the top row, and it cost 14 moves instead of 10.
The code#
Here is BFS as code. It returns the distance from S to every cell, with -1 for racks and for cells it cannot reach. The step markers [1] to [4] match the steps in the player.
from collections import deque
def bfs_distances(grid):
rows, cols = len(grid), len(grid[0])
dist = [[-1] * cols for _ in range(rows)]
queue = deque()
# [1] S gets distance 0 and joins the queue: it counts as visited from now on.
for r in range(rows):
for c in range(cols):
if grid[r][c] == "S":
dist[r][c] = 0
queue.append((r, c))
while queue:
# [2] Take the oldest cell from the front of the queue.
r, c = queue.popleft()
# [3] Each open, unvisited neighbour gets distance + 1 and joins the back.
for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
# [4] Every reachable cell has its distance; racks and cut-off cells keep -1.
return distpublic int[][] bfsDistances(String[] grid) {
int rows = grid.length, cols = grid[0].length();
int[][] dist = new int[rows][cols];
for (int[] row : dist) Arrays.fill(row, -1);
ArrayDeque<int[]> queue = new ArrayDeque<>();
// [1] S gets distance 0 and joins the queue: it counts as visited from now on.
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
if (grid[r].charAt(c) == 'S') {
dist[r][c] = 0;
queue.add(new int[] {r, c});
}
int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
while (!queue.isEmpty()) {
// [2] Take the oldest cell from the front of the queue.
int[] cell = queue.poll();
// [3] Each open, unvisited neighbour gets distance + 1 and joins the back.
for (int[] d : dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr].charAt(nc) != '#' && dist[nr][nc] == -1) {
dist[nr][nc] = dist[cell[0]][cell[1]] + 1;
queue.add(new int[] {nr, nc});
}
}
}
// [4] Every reachable cell has its distance; racks and cut-off cells keep -1.
return dist;
}vector<vector<int>> bfsDistances(vector<string> grid) {
int rows = grid.size(), cols = grid[0].size();
vector<vector<int>> dist(rows, vector<int>(cols, -1));
queue<pair<int, int>> q;
// [1] S gets distance 0 and joins the queue: it counts as visited from now on.
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
if (grid[r][c] == 'S') {
dist[r][c] = 0;
q.push({r, c});
}
int dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
while (!q.empty()) {
// [2] Take the oldest cell from the front of the queue.
auto [r, c] = q.front();
q.pop();
// [3] Each open, unvisited neighbour gets distance + 1 and joins the back.
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] != '#' && dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
// [4] Every reachable cell has its distance; racks and cut-off cells keep -1.
return dist;
}function bfsDistances(grid) {
const rows = grid.length, cols = grid[0].length;
const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1));
const queue = [];
let head = 0;
// [1] S gets distance 0 and joins the queue: it counts as visited from now on.
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (grid[r][c] === "S") {
dist[r][c] = 0;
queue.push([r, c]);
}
while (head < queue.length) {
// [2] Take the oldest cell from the front of the queue.
const [r, c] = queue[head++];
// [3] Each open, unvisited neighbour gets distance + 1 and joins the back.
for (const [dr, dc] of [[-1, 0], [0, 1], [1, 0], [0, -1]]) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] !== "#" && dist[nr][nc] === -1) {
dist[nr][nc] = dist[r][c] + 1;
queue.push([nr, nc]);
}
}
}
// [4] Every reachable cell has its distance; racks and cut-off cells keep -1.
return dist;
}The dist grid does two jobs. It stores each distance, and a value other than -1 also means "visited". JavaScript has no built-in queue, so the code keeps a head index instead of removing from the front of the array.
And here is DFS as a recursion. It counts the cells connected to S. Each call handles one cell and returns how many cells it reached.
def dfs_count(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
def visit(r, c):
# [1] Mark the cell on entry and count it.
seen[r][c] = True
count = 1
# [2] Go deeper into each open, unvisited neighbour, one at a time.
for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and not seen[nr][nc]:
count += visit(nr, nc)
# [3] No unvisited neighbour is left: return to the caller, which is the backtrack.
return count
for r in range(rows):
for c in range(cols):
if grid[r][c] == "S":
return visit(r, c)
return 0public int dfsCount(String[] grid) {
boolean[][] seen = new boolean[grid.length][grid[0].length()];
for (int r = 0; r < grid.length; r++)
for (int c = 0; c < grid[0].length(); c++)
if (grid[r].charAt(c) == 'S') return visit(grid, seen, r, c);
return 0;
}
int visit(String[] grid, boolean[][] seen, int r, int c) {
// [1] Mark the cell on entry and count it.
seen[r][c] = true;
int count = 1;
// [2] Go deeper into each open, unvisited neighbour, one at a time.
int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length() && grid[nr].charAt(nc) != '#' && !seen[nr][nc])
count += visit(grid, seen, nr, nc);
}
// [3] No unvisited neighbour is left: return to the caller, which is the backtrack.
return count;
}int visitCell(const vector<string>& grid, vector<vector<bool>>& seen, int r, int c) {
// [1] Mark the cell on entry and count it.
seen[r][c] = true;
int count = 1;
// [2] Go deeper into each open, unvisited neighbour, one at a time.
int dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < (int) grid.size() && nc >= 0 && nc < (int) grid[0].size() && grid[nr][nc] != '#' && !seen[nr][nc])
count += visitCell(grid, seen, nr, nc);
}
// [3] No unvisited neighbour is left: return to the caller, which is the backtrack.
return count;
}
int dfsCount(vector<string> grid) {
vector<vector<bool>> seen(grid.size(), vector<bool>(grid[0].size(), false));
for (int r = 0; r < (int) grid.size(); r++)
for (int c = 0; c < (int) grid[0].size(); c++)
if (grid[r][c] == 'S') return visitCell(grid, seen, r, c);
return 0;
}function dfsCount(grid) {
const rows = grid.length, cols = grid[0].length;
const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
const visit = (r, c) => {
// [1] Mark the cell on entry and count it.
seen[r][c] = true;
let count = 1;
// [2] Go deeper into each open, unvisited neighbour, one at a time.
for (const [dr, dc] of [[-1, 0], [0, 1], [1, 0], [0, -1]]) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] !== "#" && !seen[nr][nc]) count += visit(nr, nc);
}
// [3] No unvisited neighbour is left: return to the caller, which is the backtrack.
return count;
};
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (grid[r][c] === "S") return visit(r, c);
return 0;
}The recursion is short, and on small grids it is the clearest way to write DFS. On a big grid the call stack can be as deep as the number of cells, which is a problem in Python. The lab and the mistakes below show the fix: an explicit stack.
Predict what happens
Q dfs_count runs on a 7 by 7 floor with no racks. How deep does the call stack get?
Answer & explanation
Answer: D
With no walls, DFS keeps finding an unvisited neighbour, so it spirals through all 49 cells in one walk. Every call on that walk is still waiting when the last cell is entered. That is the stack you watched in the floor demo.
4. Build it: BFS and DFS yourself#
Now write both searches yourself, for Kestrel Freight's robots. The lab has two functions. Each test gives your function a floor in the same text format as the lesson, and checks the answer it returns.
shortest_steps(grid): return the fewest moves from S to G with BFS, or -1 when no path exists. You can stop as soon as G leaves the queue, or as soon as it joins.flood_fill(grid): mark every open cell that S can reach with*, using DFS with an explicit stack instead of recursion. Return the new rows. S staysS, and cells S cannot reach stay..
When a test fails, the result shows the floor, what your function returned and what it should return. A note says what that test is checking.
Three rules keep both functions correct:
- Check that a neighbour is inside the grid before you read it.
- Mark a cell visited when it joins the frontier, so it can never join twice.
- In
flood_fill, a cell is reachable even when it is far from S: keep going until the stack is empty.
Build it yourself: write the code in Python, JavaScript, Java or C++ and run the tests. It loads in your browser.
5. Use it well: choosing, costs and the classic mistakes#
What each search costs#
| Question | BFS | DFS |
|---|---|---|
| Time | O(R × C): each cell joins once and checks four neighbours | O(R × C): each cell is entered once and checks four neighbours |
| Memory | O(R × C) for the marks; the queue holds about one ring of cells | O(R × C) for the marks; the stack can hold every cell on one long walk |
| Fewest moves when every move costs the same | Yes: the first visit is the shortest | No: the first path found can be long |
| The frontier | A queue: the oldest cell first | A stack or the call stack: the newest cell first |
| Visits the same cells | Every cell connected to S | Every cell connected to S |
For a 1,000 by 1,000 floor that is about a million cells, and four million neighbour checks. That runs in well under a second in any of the four languages.
When to use which#
Use BFS when the question says "fewest moves", "shortest number of steps" or "how many minutes until it spreads". Each move must cost the same. BFS can also start from many cells at once: put them all in the queue at distance 0, and the rings spread from all of them together.
Use DFS, or BFS, when you need every connected cell: filling a region, counting separate regions, or checking whether G is reachable at all. DFS is also the base of backtracking, where you try every path, not only the shortest.
When not to use them#
Do not use BFS for "cheapest" routes when moves cost different amounts, such as a ramp that takes three times as long. Rings count moves, not cost. Dijkstra's algorithm, later in Part 3, handles that.
Do not use DFS for "fewest moves" at all. Its first path is whatever corridor it tried first. And for a single route on a very large map, both searches look at many cells that lie in the wrong direction. Map services add a sense of direction, which is a later topic.
Common mistakes#
If BFS marks a cell when it is taken out, as in r, c = queue.popleft(); seen[r][c] = True, two neighbours can both add the same cell before it is marked. On a 1,000 by 1,000 open floor the queue fills with copies, and the search slows down badly. Mark the cell at the moment you append it.
if nr < rows and nc < cols and grid[nr][nc] != "#" forgets that nr and nc can be -1. Java, C++ and JavaScript then crash or read the wrong memory. In Python it is worse: grid[-1] is the last row, so the search quietly wraps round the edge of the floor. Check 0 <= nr < rows and 0 <= nc < cols before you read the cell.
A recursive DFS makes one call per cell on its walk. Python stops at about 1,000 nested calls with RecursionError: maximum recursion depth exceeded. A 40 by 40 open floor is already deep enough. Raising the limit with sys.setrecursionlimit can crash the interpreter instead, so use an explicit stack for big grids.
queue.pop(0) on a Python list moves every other item one place left, so each pop costs O(n). On a million-cell floor that adds up to hours. Use collections.deque and popleft(), which takes O(1). In JavaScript, shift() has the same problem; keep a head index instead.
The grid is a list of rows, so a cell is grid[r][c]: row first, then column. Writing grid[c][r] works on square floors and fails on others, such as the 4 by 8 warehouse in this lesson. Name the variables r and c, never x and y, and keep rows and cols apart.
6. Recap: what to remember#
- A grid is a graph: open cells are nodes, and up, right, down and left are the neighbours.
- BFS uses a queue and spreads in rings. When every move costs the same, the first time it reaches a cell is by a shortest path.
- DFS uses a stack or recursion and goes deep, then backtracks. It reaches every connected cell, but its path is not the shortest.
- Both cost O(R × C). Mark cells when they join the frontier, check bounds before you read, and use an explicit stack on big grids in Python.
Explain the two searches in your own words, then take the checkpoint quiz. The checkpoint counts when you pass both the quiz and the lab.
Explain it back: write the idea in your own words and get feedback.
Checkpoint · The grid as a graph
Q1/2 On a grid where a robot moves up, right, down or left, which cells are the neighbours of an open cell?
Answer & explanation
Answer: B
A move goes one cell up, right, down or left. Racks and cells outside the grid are not neighbours, and diagonal moves are not allowed on this floor.
Q2/2 Which data structure holds the frontier in BFS?
Answer & explanation
Answer: A
The queue serves the oldest cell first. That is what makes BFS spread in rings of distance.
Checkpoint · How the searches move
Q1/2 A recursive DFS is visiting a cell. What does it do next?
Answer & explanation
Answer: B
DFS goes as deep as it can. The call for the neighbour runs to the end before the next neighbour is tried. Coming back after that call is the backtrack.
Q2/2 BFS takes a cell of distance 6 from the queue. Its neighbour is open and not yet visited. What distance does the neighbour get?
Answer & explanation
Answer: B
A neighbour is one move further from S: 6 + 1 = 7. The distance is fixed when the cell joins the queue.
Checkpoint · Why BFS finds the fewest moves
Q1/2 Why is the first time BFS reaches a cell always by a shortest path, when every move costs the same?
Answer & explanation
Answer: B
The queue holds cells at distance d followed by cells at distance d + 1. A shorter path would have reached the cell earlier, through a neighbour that left the queue first.
Q2/2 On the lesson's warehouse floor, BFS reaches G in 10 moves and DFS reaches it in 14. What does that show?
Answer & explanation
Answer: C
DFS follows the first corridor it tries as far as it goes. On that floor, the top row led to G the long way round. BFS checks every cell at distance 9 before any at distance 10, so its answer is the fewest moves.
Checkpoint · Marking and cost
Q1/2 Why should BFS mark a cell visited when it joins the queue, not when it leaves?
Answer & explanation
Answer: A
With the mark made late, a cell can be added once by each neighbour that finds it. The answer is still right, but the queue fills with copies and the work grows. Marking on joining keeps it to one entry for each cell.
Q2/2 A floor has R rows and C columns. What do BFS and DFS cost in time?
Answer & explanation
Answer: B
Every open cell is handled once, and each check of a neighbour is constant work. Four neighbours per cell keeps the total proportional to the number of cells.
Checkpoint · Mistakes
Q1/2 A recursive DFS in Python fills a 60 by 60 floor with no racks and crashes. What is the most likely reason?
Answer & explanation
Answer: B
On an open floor, DFS walks through every cell before any call returns. Python stops at about 1,000 nested calls, so use an explicit stack for big grids.
Q2/2 This line checks a neighbour:
if nr < rows and nc < cols and grid[nr][nc] != "#". What goes wrong in Python when nr is -1?Answer & explanation
Answer: C
-1 is less than rows, so the check passes, and a negative index in Python counts from the end of the list. Check both sides,
0 <= nr < rows and 0 <= nc < cols, then read the cell.
Review cards from this lesson.
Warm-up problems
Short problems that use what you just built: a fill, a count of regions, the fewest moves, a spread from many starts. Each takes a grid as input, as rows of text or rows of numbers.