BFS is a simple traversal algorithm which is used for many problems related to finding the shortest path. It’s commonly taught on graphs, but it can also be used with trees and grids. In fact, it can even be used with 1D arrays and numbers!

For this guide, we’ll focus on grids for visualization purposes, but you’ll also learn how to adapt the algorithm to your own problems.

BFS stands for Breadth-First Search. “Breadth-First” means the algorithm works by exploring every direction simultaneously instead of going deeper in only one direction.

Let’s say we start from the center square and can only move left, right, up, or down one step at a time. After exploring every direction once, these are the only squares we can reach in exactly 1 step:

Similarly, squares that we can move to from those reachable in 1 move would themselves be reachable in 2 moves, and so on.

Notice that we never go further until we ensure every closer square has been visited. We can say that we visit the squares in layers, and the number of steps it took us to reach a given square is its depth.

To better understand how this helps us find the shortest path, take a look at the example below, which has an obvious long way and a short way.

Since in every direction we take exactly the same number of steps, the first time we reach the target cell is always via the shortest path.

At this point, you understand the general idea of BFS, but let’s look at the implementation to learn the algorithm’s limitations and how we can use it in practice.

We are going to continue with grids; however, it’s more straightforward to use BFS with graphs or trees. That’s because those data structures explicitly include the adjacent nodes, so we don’t need to check boundaries or calculate neighbour cells.

The first data structure we need is the heart of BFS — a queue. A queue supports two main operations:

1. Adding an element at the end of the queue
2. Removing an element from the start of the queue

Both operations are O(1), unlike in an array, where removing the first element shifts every other element.

We use a queue to keep track of the order in which we need to process cells. At the front of the queue, where we take elements from, we have the cells that are closer to the starting cell, and at the end, where we push new cells, we have the furthest ones.

Python doesn’t have a separate queue data structure, so we use deque instead. Deque is a double-ended queue that can remove and insert elements at both ends in O(1) time.

q = deque([(0, 0)])  # start from the top-left cell

We also need a second data structure to store the already queued cells. This is important because if we keep adding the same cells to the queue, we’ll end up going back and forth infinitely. We also don’t want to requeue cells, since if a cell is queued, it means it was already reached from another cell that has less or equal depth, so there’s no need to reconsider it.

The most practical way to track which cells have already been queued is to use an array. In this example, we build a second grid in the same shape as the original one:

rows, cols = len(grid), len(grid[0]) # size of the grid
queued = [[False] * cols for _ in range(rows)]

q = deque([(0, 0)])
queued[0][0] = True  # mark the starting point as queued

Then we can check if a cell is queued using the cell’s indexes in O(1):

if not queued[row][col]:
    queued[row][col] = True

However, sometimes using arrays isn’t enough — e.g., if you’re working with infinite-size grids or a dictionary graph. In that case, you can use a hash set instead. It’s O(1) on average, but slower than an array because it needs to compute a hash to access data.

Let’s take a look at how the cells are going to lie in the queue. We take a cell from the front of the queue, then look at its neighbouring cells, and if they weren’t already queued, we add them to the end.

Note that we process the cells in the exact order they were discovered. You can also see that we never have more than two depth levels at the same time — the current one we’re processing, and the one we’re building from it.

Now let’s write the code to find a cell’s neighbours. We encode the four possible moves as (row, col) deltas:

dirs = [
    (0, 1),   # row+0, col+1 - right
    (1, 0),   # row+1, col+0 - down
    (0, -1),  # row+0, col-1 - left
    (-1, 0),  # row-1, col+0 - up
]

For any cell (row, col), adding each delta gives us a neighbour’s coordinates. We just need to make sure the result is still inside the grid:

for dr, dc in dirs:
    nr, nc = row + dr, col + dc

    if 0 <= nr < rows and 0 <= nc < cols:
        # (nr, nc) is a valid neighbour
        # ...

We now have everything we need to run BFS. We take a cell from the front of the queue, and add its neighbour cells to the end, skipping ones that were already queued:

while q:
    row, col = q.popleft()
    for dr, dc in dirs:
        nr, nc = row + dr, col + dc
        if 0 <= nr < rows and 0 <= nc < cols and not queued[nr][nc]:
            q.append((nr, nc))
            queued[nr][nc] = True

Here’s the full code. Right now it does nothing except traverse through each cell in order. If you run this function with a grid, it should return a 2D array with all elements set to True, which indicates that we’ve visited every cell.

from collections import deque

def bfs(grid):
    rows, cols = len(grid), len(grid[0])
    queued = [[False] * cols for _ in range(rows)]

    q = deque([(0, 0)])
    queued[0][0] = True

    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    while q:
        row, col = q.popleft()

        for dr, dc in dirs:
            nr, nc = row + dr, col + dc

            if 0 <= nr < rows and 0 <= nc < cols and not queued[nr][nc]:
                q.append((nr, nc))
                queued[nr][nc] = True

    return queued

Let’s modify the code to make it useful. We are going to find the cell closest to the top-left corner that contains a 1. We can do this by checking whether a cell taken from the queue has the value 1 in the grid:

while q:
    row, col = q.popleft()

    if grid[row][col] == 1:
        return (row, col)

    # ...

return None

If there is no 1 in the grid, the while loop will finish without returning a value. In this case, we return None instead of queue to signal that we couldn’t find the target value.

Here’s the visualization of our search algorithm, where blue represents queued cells.

You can see that we don’t return the cell as soon as we discover it, so we even had multiple 1s in the queue at some point. Isn’t it suboptimal?

Yes, it is. Let’s fix it by checking the value right before we add it to the queue instead:

while q:
  row, col = q.popleft()

  for dr, dc in dirs:
    nr, nc = row + dr, col + dc

    if 0 <= nr < rows and 0 <= nc < cols and not queued[nr][nc]:
      if grid[nr][nc] == 1: # <-- now we check here
        return (nr, nc)

      q.append((nr, nc))
      queued[nr][nc] = True

return None

Ugghhhhh..? Heeey!!

It didn’t check the (0, 0) cell. Our optimization introduced a bug because we only check the discovered cells, but the starting cell was never discovered by any other cells. It’s just initialized in the queue from the beginning:

q = deque([(0, 0)])

We can fix this bug by checking the starting cell explicitly at the start of the function:

def bfs(grid):
    if grid[0][0] == 1:
        return (0, 0)

This edge case can catch a lot of beginners off guard. That’s why I recommend processing cells after we take them from the queue. It’s more idiomatic to think of the queue as the processing queue and it avoids nested if statements, which makes it cleaner.

Also, notice that all this time we assumed that the input grid is not empty.

Now, let’s talk about propagation. It’s often useful to carry some information from the previous cells we passed through. We can do that by storing the data along the cell coordinates in the queue.

For example, we can count the number of steps it took us to reach a cell. The starting cell would get value 0, as we don’t need to move to reach it:

q = deque([((0, 0), 0)])

We’ll unpack the values in the queue like this:

(row, col), step = q.popleft()

if grid[0][0] == 1:
  return step

And then counting steps is as simple as adding 1 to the previous cell’s step number:

q.append(((nr, nc), step + 1))
queued[nr][nc] = True

You might be tempted to use this pattern to track the entire path. Indeed, you can store the path as an array alongside the cell in the queue:

start = (0, 0)
q = deque([(start, [start])]) # ((row, col), path)

Appending to the path would become:

q.append(((nr, nc), path + [(nr, nc)]))

This works, but you will have to copy the path on every step, and most of the cells would have the same paths that only differ at the end, which blows up the time complexity and wastes memory.

A better approach is to just remember where each cell came from, instead of dragging the whole path along.

parent = [[None] * cols for _ in range(rows)]

Now the queue stays lean, no bloated arrays riding along with every entry:

parent[nr][nc] = (row, col)
queue.append((nr, nc))

Once we hit the destination, we can walk backward through those pointers to rebuild the path:

path = []
node = (nr, nc)

while node is not None:
  path.append(node)
  r, c = node
  node = parent[r][c]

BFS also comes with limitations. Let’s recall the example with short and long paths, but this time some cells will turn us into a turtle, and some into a rabbit.

As you can see, the path with the turtles is still considered faster. That’s because BFS doesn’t track the cost of the steps. In graph terms, we say that BFS only works on unweighted graphs.

For such problems, we could use Dijkstra’s algorithm, which is a modified BFS, but we are not going to talk about it in this guide.

So far, we’ve only talked about adjacent cells but BFS can work with anything as long as:

1. Each step costs exactly the same.
2. There is no reason to reconsider already visited elements.

One good example is a knight moving on a chessboard:

There’s one property of BFS we haven’t talked about yet: multi-source BFS — a technique that lets us start from multiple points.

To do that, we just initialize the queue with multiple elements:

q = deque([(1, 4), (2, 2), (4, 1), (3, 4)])

This can be quite useful when we need to precompute data. For example, if we need to find the distance to the closest 1 in the grid for every cell, we can just run multi-source BFS from every 1 and save the distance in a separate grid:

def bfs(grid):
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]

    q = deque()
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 1:
                dist[row][col] = 0
                q.append((row, col))

    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    while q:
        row, col = q.popleft()
        for dr, dc in dirs:
            nr, nc = row + dr, col + dc
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1:
                dist[nr][nc] = dist[row][col] + 1
                q.append((nr, nc))

    return dist

The last thing I want to mention is an optimization trick. If you remember, the queue only holds two levels at the same time:

1. Current level we’re currently processing
2. The level we’re building from the current one

At the beginning, we only have one level. As we move through the current level, we build the second one on top. When we finish processing the current one, we only left with the next level elements.

That means we can track current depth without storing it in the queue for every element by incrementing depth when we finish processing a layer:

depth = 0

while q:
  level_size = len(q)

  for _ in range(level_size):
    row, col = q.popleft()
    # ...

  depth += 1

The time complexity of BFS is O(V + E), where

• V is the number of vertices
• E is the number of edges

Visiting every node exactly once contributes the V, and checking each node’s neighbors contributes the E.

In grids, each cell has a constant number of neighbors (4), so the time complexity simplifies to O(rows × cols).

The only thing you actually need to memorize is that BFS uses a queue. Everything else can be derived by asking the right questions.

Here are some LeetCode problems to practice BFS:

• 733. Flood Fill
• 200. Number of Islands
• 994. Rotting Oranges