Breadth-first and depth-first search explained

Breadth-first vs depth-first search explained with live robot demos: a stack or a queue, why BFS finds the shortest path and DFS may not, BFS vs DFS in Python, time complexity O(V + E), and when to use each for A level Computer Science.

Guidefree, runs in your browser

Breadth-first search (BFS) and depth-first search (DFS) are the two basic ways to explore a graph: a map of places joined by paths. Both visit every place they can reach, once each. They differ only in which place they go to next, and that one choice decides whether they find the shortest route, how much they have to look at, and how much they have to remember. They sit inside maze solvers, route planners, web crawlers and puzzle solvers. On this page a small robot searches a maze and a 2 metre mat, and each demo below is a real program you can change and run.

On the mat, blue squares are places the search has visited, yellow squares are places it has found but not yet visited (they are waiting their turn), and the red line is the route it found.

The idea in one line

depth-first:   next, take the place you found most recently
breadth-first: next, take the place you found longest ago

Everything else is the same for both:

1. Put the start in a collection of places that are waiting.
2. Take one place out. If it has been visited already, skip it. Otherwise visit it, and add each of its neighbours that has not been visited.
3. Repeat until the goal comes out, or nothing is left waiting.

Taking the newest place means the waiting places are kept on a stack (last in, first out). The search keeps following the path it has just found, deeper and deeper, and only goes back when it runs out of new places. Going back is called backtracking.

Taking the oldest place means they are kept in a queue (first in, first out). The search finishes every place one step from the start before any place two steps away, then two before three, spreading out in rings like the ripples from a stone dropped in a pond.

A worked example

Six places, joined like this, with neighbours always tried in alphabetical order:

A --- B --- C
|     |
D --- E --- F

Depth-first from A, with the stack written bottom to top, so the top is on the right. Neighbours are pushed in reverse order, so the first one in alphabetical order ends up on top:

Breadth-first from A. Here a place is marked when it joins the queue, so it can never be waiting twice:

Depth-first visits A, B, C, E, D, F. Breadth-first visits A, B, D, C, E, F: first the places one edge from A, then two, then three. Both reach all six. But depth-first first reached D by A, B, E, D, three edges, when D is one edge from A. Breadth-first always reaches a place first by the fewest edges, which is why it finds shortest routes.

Depth-first in a maze

The maze is made of 20 cm blocks on a 1 metre mat. The program keeps only a model of it: five rows of five cells, # for a block, the robot at S and the goal at G. From each cell the search tries up, right, down and left, in that order.

Depth-first search is most often written with recursion: dfs visits a cell, then calls itself on each neighbour. The computer's call stack is the stack, so backtracking is a call returning False. The list path holds the way back from the current cell to S, and is drawn in red. The chart shows how many steps that path is.

from bugbot import *
connect()

# change ORDER and press Run
# the order to try the ways out of a cell
ORDER = ["up", "right", "down", "left"]

MAZE = ["...#G",       # row 0, the top
        ".###.",
        ".#...",
        ".#.#.",
        "S...."]       # row 4, the robot
MOVE = {"up": (-1, 0), "right": (0, 1),
        "down": (1, 0), "left": (0, -1)}

def cm(cell):
    # the centre of a cell, in cm on the mat
    row, col = cell
    return (10 + 20 * col, 90 - 20 * row)

def show():
    draw("visited", [cm(c) for c in visited],
         "blue", "squares", 16)
    draw("path", [cm(c) for c in path],
         "red", "line", 2)
    plot("steps from S", len(path) - 1)
    wait(0.4)

visited = set()
path = []            # the way back, as a stack

def dfs(row, col):
    if not (0 <= row < 5 and 0 <= col < 5):
        return False             # off the grid
    if MAZE[row][col] == "#":
        return False             # a block
    if (row, col) in visited:
        return False             # been here
    visited.add((row, col))
    path.append((row, col))
    show()
    if MAZE[row][col] == "G":
        return True
    for way in ORDER:
        dr, dc = MOVE[way]
        if dfs(row + dr, col + dc):
            return True
    path.pop()                   # a dead end:
    show()                       # back up one
    return False

dfs(4, 0)
print("visited:", len(visited), "cells")
print("route:", len(path) - 1, "steps")

The chart is the shape of depth-first search: it climbs from 0 to 6 as the search goes up the left side and along the top, falls back to 0 as it backs out of the dead end one cell at a time, then climbs to 8 on the way to G. Nothing ever looks ahead. The search only learns that a way is a dead end by walking to the end of it.

The order it tries the ways matters a great deal. Put "right" first and the search runs along the bottom and up the right side, visiting only 9 cells. Try ["left", "down", "right", "up"] and it visits 12. The route is 8 steps every time, but that is luck: this maze has only two routes from S to G, and both are 8 steps long.

Breadth-first in the same maze

Now the same maze with a queue. deque is Python's double-ended queue: popleft() takes from the front quickly. The chart shows how many steps from S each cell is, as it comes off the front of the queue. When the search is over, the robot drives the route it found.

from bugbot import *
from collections import deque
connect()

# change ORDER and press Run
# the order to try the ways out of a cell
ORDER = ["up", "right", "down", "left"]

MAZE = ["...#G",       # row 0, the top
        ".###.",
        ".#...",
        ".#.#.",
        "S...."]       # row 4, the robot
START = (4, 0)
GOAL = (0, 4)
MOVE = {"up": (-1, 0), "right": (0, 1),
        "down": (1, 0), "left": (0, -1)}

def cm(cell):
    # the centre of a cell, in cm on the mat
    row, col = cell
    return (10 + 20 * col, 90 - 20 * row)

def neighbours(cell):
    out = []
    for way in ORDER:
        dr, dc = MOVE[way]
        r, c = cell[0] + dr, cell[1] + dc
        if 0 <= r < 5 and 0 <= c < 5:
            if MAZE[r][c] != "#":
                out.append((r, c))
    return out

queue = deque([START])
came = {START: None}     # discovered, and parent
steps = {START: 0}       # steps from S
done = []                # taken off the queue
while queue:
    cell = queue.popleft()           # the front
    done.append(cell)
    for n in neighbours(cell):
        if n not in came:
            came[n] = cell           # mark it now
            steps[n] = steps[cell] + 1
            queue.append(n)          # join the back
    draw("visited", [cm(c) for c in done],
         "blue", "squares", 16)
    draw("queue", [cm(c) for c in queue],
         "yellow", "squares", 8)
    plot("steps from S", steps[cell])
    wait(0.4)
    if cell == GOAL:
        break

route = []
cell = GOAL
while cell is not None:
    route.append(cell)
    cell = came[cell]
route.reverse()
draw("route", [cm(c) for c in route],
     "red", "line", 2)
print("visited:", len(done), "cells")
print("route:", len(route) - 1, "steps")

# drive it, a cell at a time
x0, y0 = cm(START)
for cell in route[1:]:
    tx, ty = cm(cell)
    x, y = position()        # cm from the start
    dx = tx - x0 - x
    dy = ty - y0 - y
    if dx > 1:
        right(80, distance=dx)
    elif dx < -1:
        left(80, distance=-dx)
    if dy > 1:
        forward(80, distance=dy)
    elif dy < -1:
        backward(80, distance=-dy)
x, y = position()
print("stopped at", round(x0 + x), round(y0 + y))

Every cell records the cell it was found from, its parent. The route is read backwards from G by following the parents to S, then reversed. Because each cell was first found from a cell one ring nearer the start, that route is always as short as any route can be, counted in steps.

In this maze breadth-first did more work than depth-first: 18 cells against 15. G is the only cell 8 steps from S, the furthest of all, so breadth-first has to finish every nearer ring first. Change ORDER here and it still visits all 18 and still finds an 8 step route. Breadth-first does not depend on luck.

On open ground

A maze with narrow corridors hides the biggest difference between the two. On open ground depth-first search has many more ways to go wrong. This mat is 2 metres square with two walls, cut into 10 cm cells. The walls and the edge are grown by 10 cm, and any cell whose centre falls inside them is left out, which leaves 234 cells the robot could reach. The goal is a cell in the green corner.

The program below does both searches, and one line decides which: pop() takes the newest cell from the end of the deque, making it a stack, and popleft() takes the oldest from the front, making it a queue. Both mark a cell visited when it is taken out, like the depth-first trace above, so the same cell can be waiting more than once. The chart counts the cells visited and the cells waiting.

from bugbot import *
from collections import deque
connect()

# change MODE or GOAL and press Run
MODE = "dfs"      # "dfs": a stack   "bfs": a queue
GOAL = (17, 17)   # the green corner, in cells

CELL = 10                # each cell is 10 cm
START = (3, 3)           # the robot, at 30, 30 cm
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]
# up, right, down, left
STEPS = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def cm(c):
    return (c[0] * CELL, c[1] * CELL)

def blocked(c):
    # walls and mat edge, grown by 10 cm
    x, y = cm(c)
    if not (10 < x < 190 and 10 < y < 190):
        return True
    for wx, wy, ww, wh in WALLS:
        if (wx - 10 < x < wx + ww + 10 and
                wy - 10 < y < wy + wh + 10):
            return True
    return False

def show():
    draw("visited", [cm(c) for c in came],
         "blue", "squares", 8)
    draw("waiting", [cm(c) for c, p in frontier],
         "yellow", "squares", 5)
    plot("cells visited", len(came))
    plot("cells waiting", len(frontier))
    wait(0.1)

frontier = deque([(START, None)])  # (cell, from)
came = {}                # visited, and parent
while frontier:
    if MODE == "dfs":
        cell, parent = frontier.pop()      # newest
    else:
        cell, parent = frontier.popleft()  # oldest
    if cell in came:
        continue
    came[cell] = parent
    if cell == GOAL:
        break
    # add in reverse, so a stack tries up first
    for dx, dy in reversed(STEPS):
        n = (cell[0] + dx, cell[1] + dy)
        if n not in came and not blocked(n):
            frontier.append((n, cell))
    if len(came) % 4 == 0:
        show()
show()

route = []
c = GOAL
while c is not None:
    route.append(cm(c))
    c = came[c]
draw("route", route, "red", "line", 2)
print(MODE, "visited:", len(came), "cells")
print("route:", (len(route) - 1) * CELL, "cm")

Depth-first never hit a dead end here. Every one of the 85 cells it visited is on its route. It kept going up, then right, then down, as the order told it, and only stopped when it stumbled on the goal. At the top right it passed the cell next to the goal and carried on, because at that moment "right" came before "down".

Here is the same program with MODE = "bfs".

from bugbot import *
from collections import deque
connect()

# change MODE or GOAL and press Run
MODE = "bfs"      # "dfs": a stack   "bfs": a queue
GOAL = (17, 17)   # the green corner, in cells

CELL = 10                # each cell is 10 cm
START = (3, 3)           # the robot, at 30, 30 cm
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]
# up, right, down, left
STEPS = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def cm(c):
    return (c[0] * CELL, c[1] * CELL)

def blocked(c):
    # walls and mat edge, grown by 10 cm
    x, y = cm(c)
    if not (10 < x < 190 and 10 < y < 190):
        return True
    for wx, wy, ww, wh in WALLS:
        if (wx - 10 < x < wx + ww + 10 and
                wy - 10 < y < wy + wh + 10):
            return True
    return False

def show():
    draw("visited", [cm(c) for c in came],
         "blue", "squares", 8)
    draw("waiting", [cm(c) for c, p in frontier],
         "yellow", "squares", 5)
    plot("cells visited", len(came))
    plot("cells waiting", len(frontier))
    wait(0.1)

frontier = deque([(START, None)])  # (cell, from)
came = {}                # visited, and parent
while frontier:
    if MODE == "dfs":
        cell, parent = frontier.pop()      # newest
    else:
        cell, parent = frontier.popleft()  # oldest
    if cell in came:
        continue
    came[cell] = parent
    if cell == GOAL:
        break
    # add in reverse, so a stack tries up first
    for dx, dy in reversed(STEPS):
        n = (cell[0] + dx, cell[1] + dy)
        if n not in came and not blocked(n):
            frontier.append((n, cell))
    if len(came) % 4 == 0:
        show()
show()

route = []
c = GOAL
while c is not None:
    route.append(cm(c))
    c = came[c]
draw("route", route, "red", "line", 2)
print(MODE, "visited:", len(came), "cells")
print("route:", (len(route) - 1) * CELL, "cm")

Breadth-first had to look at nearly the whole mat, because the green corner is one of the furthest points from the robot. Move the goal and the balance changes. These are from this program, run with each GOAL:

With the goal 20 cm to the right, depth-first sets off upwards, wanders over most of the mat and returns a route 88 times longer than it needs to be. Breadth-first finds it after 9 cells. With the goal straight up, the direction depth-first tries first, it goes straight there and does a fifth of the work. Depth-first is quick when its first guess is right and very poor when it is wrong, and it never knows which.

Memory. On this mat the stack grew to 99 cells and the queue never passed 17. The queue only holds the current ring, and on a grid a ring is small. It is the other way round on a graph where every place has many neighbours. In a tree where every place leads to 10 more, the sixth ring has a million places, and breadth-first has to hold them all in its queue, while depth-first holds the path it is on and the places beside it, about 60.

When steps cost different amounts

Breadth-first finds the route with the fewest steps. That is the shortest route only if every step costs the same. Here the orange patch under the second wall is carpet, where the robot is three times slower, so a step onto it costs 3 and any other step costs 1.

from bugbot import *
from collections import deque
import heapq
connect()

# change MODE or SLOW and press Run
MODE = "bfs"      # "bfs" or "dijkstra"
SLOW = 3          # a carpet cell costs this many

CELL = 10                # each cell is 10 cm
START = (3, 3)           # the robot, at 30, 30 cm
GOAL = (17, 17)          # the green corner
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]
STEPS = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def cm(c):
    return (c[0] * CELL, c[1] * CELL)

def blocked(c):
    # walls and mat edge, grown by 10 cm
    x, y = cm(c)
    if not (10 < x < 190 and 10 < y < 190):
        return True
    for wx, wy, ww, wh in WALLS:
        if (wx - 10 < x < wx + ww + 10 and
                wy - 10 < y < wy + wh + 10):
            return True
    return False

def carpet(c):
    # a slow patch under the second wall
    return 10 <= c[0] <= 15 and 6 <= c[1] <= 7

def cost(c):
    return SLOW if carpet(c) else 1

rug = [(x, y) for x in range(21)
       for y in range(21)
       if carpet((x, y)) and not blocked((x, y))]
draw("carpet", [cm(c) for c in rug],
     "orange", "squares", 10)

g = {START: 0}           # cost from the start
came = {START: None}
done = set()
if MODE == "bfs":
    frontier = deque([START])
else:
    frontier = [(0, START)]
while frontier:
    if MODE == "bfs":
        cell = frontier.popleft()
    else:
        d, cell = heapq.heappop(frontier)
        if cell in done:
            continue
    done.add(cell)
    plot("cost from the start", g[cell])
    if len(done) % 4 == 0:
        draw("visited", [cm(c) for c in done],
             "blue", "squares", 6)
        wait(0.1)
    if cell == GOAL:
        break
    for dx, dy in STEPS:
        n = (cell[0] + dx, cell[1] + dy)
        if blocked(n) or n in done:
            continue
        new = g[cell] + cost(n)
        if MODE == "bfs":
            if n not in came:        # first found
                g[n] = new
                came[n] = cell
                frontier.append(n)
        elif new < g.get(n, 1e9):    # cheaper
            g[n] = new
            came[n] = cell
            heapq.heappush(frontier, (new, n))

route = []
c = GOAL
while c is not None:
    route.append(cm(c))
    c = came[c]
draw("route", route, "red", "line", 2)
print(MODE, "route:", len(route) - 1, "steps,",
      "cost", g[GOAL])

The chart shows the cost of each cell as it comes out. With breadth-first the line goes down 22 times: it takes cells in order of steps, and a cell a few steps away across the carpet can cost more than one further away round it. With MODE = "dijkstra" the line never goes down. That is Dijkstra's algorithm: breadth-first search with the queue replaced by a priority queue (heapq), which always hands out the cheapest cell next. Set SLOW = 1 and Dijkstra returns a 40 step route costing 40, the same length as breadth-first's, because with every step costing 1, fewest steps and cheapest are the same thing. A* search goes one step further and adds a guess at the cost still to go.

BFS and DFS in Python

The demos write each search out for a grid. Here they are as functions for any graph stored as an adjacency list: a dictionary giving each place's neighbours. This is the six-place graph from the worked example.

from collections import deque

GRAPH = {"A": ["B", "D"], "B": ["A", "C", "E"],
         "C": ["B"], "D": ["A", "E"],
         "E": ["B", "D", "F"], "F": ["E"]}

def dfs(graph, start):
    seen = set()
    order = []
    stack = [start]
    while stack:
        v = stack.pop()                  # the newest
        if v in seen:
            continue
        seen.add(v)
        order.append(v)
        for n in reversed(graph[v]):
            if n not in seen:
                stack.append(n)
    return order

def dfs_recursive(graph, v, seen=None):
    if seen is None:
        seen = []
    seen.append(v)
    for n in graph[v]:
        if n not in seen:
            dfs_recursive(graph, n, seen)
    return seen

def bfs(graph, start):
    parent = {start: None}   # found, and from where
    order = []
    queue = deque([start])
    while queue:
        v = queue.popleft()              # the oldest
        order.append(v)
        for n in graph[v]:
            if n not in parent:
                parent[n] = v
                queue.append(n)
    return order, parent

def path(parent, goal):
    out = []
    while goal is not None:
        out.append(goal)
        goal = parent[goal]
    return out[::-1]

print(dfs(GRAPH, "A"))
print(dfs_recursive(GRAPH, "A"))
order, parent = bfs(GRAPH, "A")
print(order)
print(path(parent, "F"))

It prints ['A', 'B', 'C', 'E', 'D', 'F'] twice, then ['A', 'B', 'D', 'C', 'E', 'F'], then the shortest route to F, ['A', 'B', 'E', 'F']. A Python list is a good stack, because append and pop work at the end. It is a poor queue: pop(0) moves every other item along one place. deque takes from either end quickly. Keeping the visited places in a set or a dictionary makes the "seen it?" check quick however many there are. The recursive version is shorter, but Python stops a recursion about 1,000 calls deep, so on a large graph use the stack.

Which one to use

Both visit each place at most once and look along each link at most twice, once from each end. With an adjacency list, the time for either grows with V + E, the number of places plus the number of links, written O(V + E). With an adjacency matrix, finding a place's neighbours means reading its whole row, so the time grows with V², O(V²).

Questions

What is the difference between breadth-first and depth-first search?

Only the order in which they visit the places they have found. Depth-first takes the newest one next, using a stack, so it follows one path as far as it goes before backtracking. Breadth-first takes the oldest one next, using a queue, so it finishes everything one step from the start before anything two steps away.

When should you use BFS instead of DFS?

Use breadth-first when you need the shortest route and every step costs the same, such as the fewest moves on a grid or the fewest hops across a network, or when you want the nearest of something. Use depth-first when any route will do, when you need to visit everything, or when you are checking whether a path or a cycle exists, particularly on a graph so wide that a breadth-first queue would not fit in memory.

Which is best, DFS or BFS?

Neither, in general. On the open mat on this page, depth-first found a goal 20 cm away only after 192 cells and returned a 1,760 cm route, while breadth-first took 9 cells. With the goal straight up, the way depth-first tries first, depth-first took 15 cells and breadth-first 74, and both found the same 140 cm route. Breadth-first is the safe choice for shortest routes; depth-first is often faster and uses less memory when the graph is wide.

Does depth-first search find the shortest path?

Not reliably. It returns the first route it happens on, which depends on the order it tries the neighbours. On this page it returned an 840 cm route where 400 cm was possible. Breadth-first always finds the route with the fewest steps.

Is Dijkstra's algorithm a BFS or DFS?

It is breadth-first search with the queue replaced by a priority queue. Instead of taking the place found longest ago, it takes the place that is cheapest to reach so far. When every step costs the same, it visits places in the same order as breadth-first. When steps cost different amounts, it finds the cheapest route where breadth-first finds only the one with fewest steps: on the carpet demo here, 44 steps costing 44 against breadth-first's 40 steps costing 50.

Is DFS or BFS greedy?

Neither. A greedy search chooses its next step by a guess at which one looks closest to the goal. BFS and DFS are uninformed searches: they never look at where the goal is, and follow their stack or queue. Greedy best-first search and A* are informed searches that use such a guess.

What is the time complexity of BFS and DFS?

Both are O(V + E) with an adjacency list, where V is the number of vertices and E the number of edges, because each vertex is visited once and each edge is looked along once from each end. With an adjacency matrix both are O(V²). In the worst case both need memory for O(V) vertices.

Why does BFS use a queue and DFS use a stack?

A queue hands out places in the order they were found, so places near the start, found early, come out before places further away. A stack hands out the most recent place, which is a neighbour of the place just visited, so the search keeps going deeper. Swapping popleft() for pop() in the open ground demo turns one into the other.

Can depth-first search go round in circles?

Yes, if it does not record which places it has visited. The six-place graph on this page has a loop, A, B, E, D, A, and a search with no visited set would go round it forever. Every version on this page skips places it has already visited.

How do you write BFS and DFS in Python?

For breadth-first, use collections.deque as the queue: append to join the back and popleft to take from the front. For depth-first, use a plain list as the stack with append and pop, or write a function that calls itself for each unvisited neighbour. Keep the visited places in a set or dictionary, and record each place's parent if you want the route. The functions on this page do each in under 20 lines.

Are BFS and DFS on the A level Computer Science specification?

Yes. AQA's A level (7517) asks you to trace breadth-first and depth-first graph traversal and give typical uses (section 4.3.1.1). OCR's A level (H446) includes depth-first (post-order) and breadth-first traversal in its algorithms section (2.3.1). Neither appears in the GCSE specifications.

Learn it step by step

These lessons build the same ideas one at a time, each with tasks the simulator marks.

1. A4.3 Depth-first traversal Trees and graphs, A level
2. A4.4 Breadth-first traversal Trees and graphs, A level
3. A2.10 Project: out of the dead end Recursion and computational thinking, A level
4. 2.6 Project: the maze Sensing, Robot club