Pointer Walk

Graph Traversal: BFS and DFS

Two ways to visit everything in a graph. One spreads out in rings using a queue. The other dives deep using a stack.

AlgorithmsBeginner9 min read

Visiting everything, once

A graph is a set of nodes joined by edges. The most basic thing to do with one is to start somewhere and visit every node you can reach.

That one operation answers a lot of questions. Is there a route from A to H? Which web pages can be reached from this one? Which cells does this paint-bucket fill touch? Which files does this program depend on?

A list can be walked from start to end. A graph has no start and no end, and it can have loops. So two things are needed:

  • A "seen" set, so that no node is visited twice and loops do not trap you.
  • A to-do list of nodes that have been discovered but not yet visited.

The surprising part: the whole difference between the two famous methods is which end of the to-do list you take from.

Breadth-first search (BFS)

The to-do list is a queue. Take from the front, add to the back. The node that has waited longest goes next.

Breadth-first searchInteractive
ABCDEFGH

Queue (front on the left)

A

Visited, in order

Start. Breadth-first: keep a queue of nodes to visit. Take from the front, add new discoveries at the back. Start with A in the queue.

Visited
0 / 8

The order was A, B, C, D, E, F, G, H. Everything one step from A, then everything two steps away, then three. It spreads out like a ripple in water.

python
from collections import deque

def bfs(graph, start):
    seen = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()          # oldest first
        visit(node)
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)
                queue.append(neighbour)

Depth-first search (DFS)

The to-do list is a stack. Take from the top, add to the top. The node discovered most recently goes next.

Depth-first searchInteractive
ABCDEFGH

Stack (top on the right)

A

Visited, in order

Start. Depth-first: keep a stack of nodes to visit. Take from the top, add new discoveries on top. Start with A on the stack.

Visited
0 / 8

The order was A, B, D, E, H, F, C, G. It went down one branch as far as it could, and only came back for C at the end.

python
def dfs(graph, start):
    seen = {start}
    stack = [start]
    while stack:
        node = stack.pop()              # newest first
        visit(node)
        for neighbour in reversed(graph[node]):
            if neighbour not in seen:
                seen.add(neighbour)
                stack.append(neighbour)

Change popleft() to pop() and a breadth-first search becomes a depth-first one. See Stacks and Queues.

DFS is often written with recursion instead. The call stack then does the job of the stack.

python
def dfs(graph, node, seen):
    seen.add(node)
    visit(node)
    for neighbour in graph[node]:
        if neighbour not in seen:
            dfs(graph, neighbour, seen)

Try both

Breadth-first searchInteractive
Method
ABCDEFGH

Queue (front on the left)

A

Visited, in order

Start. Breadth-first: keep a queue of nodes to visit. Take from the front, add new discoveries at the back. Start with A in the queue.

Visited
0 / 8

What they cost

Both visit each node once and look along each edge once (twice if edges go both ways). The time is the number of nodes plus the number of edges. Neither is faster than the other.

They differ in memory:

  • BFS holds a whole "ring" of nodes at once. In a wide graph that can be a large share of all the nodes.
  • DFS holds one path from the start, plus the branches left to try. In a deep graph that can be long, and the recursive form can overflow the stack.

Which to use

You wantUseWhy
The shortest route, in number of stepsBFSIt reaches nodes in order of distance
Everything within k stepsBFSStop after k rings
To know whether a route exists at allEitherBoth visit everything reachable
To detect a loopDFSA loop shows up as meeting a node that is still on the current path
An order that respects dependenciesDFSA node is finished only after everything it leads to
To explore all choices in a puzzle, undoing as you goDFSGoing deep and backing up is exactly backtracking
To solve a mazeEitherDFS finds a way out. BFS finds the shortest

Example

Friends of friends

A social network wants to suggest "people you may know": everyone exactly two connections away from you.

BFS is the natural fit. The first ring is your friends. The second ring is their friends who are not already yours. Stop there. DFS would wander far along one chain of acquaintances before coming back.

The mistake everyone makes once

Forgetting the "seen" set. In a tree it does not matter, since there is only one way to reach each node. In a graph with a loop, A leads to B, B leads back to A, and the search never ends.

Mark a node as seen when you add it to the to-do list, not when you take it out. Otherwise the same node can be added many times before its turn comes.

Key takeaways

  • Traversal means visiting every reachable node once, using a to-do list and a set of nodes already seen.
  • Breadth-first search uses a queue and spreads out in rings, nearest nodes first.
  • Depth-first search uses a stack, or recursion, and follows one path to its end before backing up.
  • BFS finds the route with the fewest steps. DFS suits loops, dependency order and backtracking.
  • Both take time proportional to nodes plus edges. Without a seen set, a loop makes either run forever.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress