Graph Traversal: BFS and DFS

What a graph is

A graph is a collection of things and the connections between them. The things are called nodes (or vertices). The connections are called edges. A road map is a graph: cities are nodes, roads are edges. A social network is a graph: people are nodes, friendships are edges.

We usually write the count of nodes as V and the count of edges as E. These two letters show up in every complexity claim below, so keep them in mind: V is how many nodes, E is how many connections.

Edges can be undirected (the connection goes both ways, like a two-way friendship) or directed (one-way, like “A follows B” on a social app). For this lesson we use undirected graphs unless stated otherwise, but everything works the same for directed ones.

A traversal means visiting the nodes in some order, following edges, until you have seen everything reachable. This lesson covers the two fundamental traversals every programmer learns: breadth-first search (BFS) and depth-first search (DFS). They differ only in the order they visit nodes, but that difference decides what problems each one solves.

Representing a graph in Python

Before we can traverse a graph we need to store one. The most common representation is an adjacency list: a dictionary that maps each node to the list of its neighbors (the nodes directly connected to it by an edge).

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}
# graph["B"] -> ['A', 'D', 'E']  (B's neighbors)

Every example below uses this graph. It is undirected, so each line is a two-way edge: A connects to B and B connects back to A.

graph TD
    A --- B
    A --- C
    B --- D
    B --- E
    C --- F
    E --- F

A quick note on why a dictionary of lists is a good choice: looking up one node’s neighbors is instant, and the total storage is proportional to V + E (one dictionary entry per node, and each edge contributes to two neighbor lists). We say the space is O(V + E). The Big-O notation just means “grows in proportion to”; O(V + E) means the memory used scales with the number of nodes plus the number of edges, nothing worse.

The visited set: the one idea both algorithms share

Graphs can have cycles (a path that loops back to where it started). In our graph, A to B to E to F to C to A is a cycle. If a traversal followed edges blindly it would go around that loop forever.

The fix is a visited set: a collection that remembers every node we have already seen. A set in Python is a container that holds unique items and can answer “is this item in here?” in constant time, written O(1) (the check takes the same tiny amount of time no matter how big the set is). Before we process a node we check the visited set; if the node is already there, we skip it. Every correct graph traversal keeps one: without it, the program loops forever on any graph with a cycle, and with it, each node is handled exactly once.

Breadth-first search (BFS)

Breadth-first means we explore the graph in layers, spreading outward from a starting node. First we visit the start. Then all nodes one edge away. Then all nodes two edges away. And so on. It is like a ripple expanding across a pond.

To do this we need a queue: a line where items are removed in the same order they were added, first-in-first-out (FIFO). Think of a checkout line: whoever joined first is served first. Python’s collections.deque is an efficient queue; append adds to the back, popleft removes from the front, both O(1).

The set of nodes we are about to process at each layer is called the frontier. BFS repeatedly takes the front node off the queue, looks at its neighbors, and adds any unseen neighbors to the back of the queue.

from collections import deque

def bfs(graph, start):
    visited = {start}          # mark start as seen immediately
    queue = deque([start])     # the queue holds nodes waiting to be processed
    order = []                 # the order we actually visit nodes
    while queue:
        node = queue.popleft()     # take from the FRONT (FIFO)
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)   # mark on ENQUEUE (see pitfalls)
                queue.append(neighbor)  # add to the BACK
    return order

print(bfs(graph, "A"))
# -> ['A', 'B', 'C', 'D', 'E', 'F']

Notice the visit order: A (layer 0), then B and C (layer 1, both one edge from A), then D, E, F (layer 2). BFS finishes a whole layer before touching the next, spreading outward from A one ring at a time:

graph TD
    subgraph L0["Layer 0 (start)"]
        A
    end
    subgraph L1["Layer 1"]
        B
        C
    end
    subgraph L2["Layer 2"]
        D
        E
        F
    end
    A --- B
    A --- C
    B --- D
    B --- E
    C --- F

BFS step-by-step trace

Trace bfs(graph, "A") one loop iteration at a time. Each row shows the queue and the visited set after that step completes. When we pop a node we scan its neighbors in the order they appear in the adjacency list and enqueue the unseen ones.

The queue empties, the loop stops. Follow the “Popped” column top to bottom and you get the visit order A, B, C, D, E, F. Watch how at step 2, B’s neighbor A is skipped (already visited), and at steps 4-6 nothing new is enqueued because every neighbor is already known.

BFS gives the shortest path in an unweighted graph

Because BFS reaches every node in layer order, the first time it sees a node is by a path with the fewest possible edges. In a graph where every edge counts as one step (unweighted), that is the shortest path. This is BFS’s headline feature. To recover the path, remember which node you came from when you first enqueue each node.

from collections import deque

def shortest_path(graph, start, goal):
    if start == goal:
        return [start]
    visited = {start}
    parent = {start: None}     # remembers how we first reached each node
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                if neighbor == goal:
                    # walk backwards from goal to start, then reverse
                    path = [goal]
                    while parent[path[-1]] is not None:
                        path.append(parent[path[-1]])
                    return path[::-1]
                queue.append(neighbor)
    return None                # goal not reachable

print(shortest_path(graph, "A", "F"))
# -> ['A', 'C', 'F']

A to F is two edges (A-C-F), and BFS finds exactly that. DFS, below, would not guarantee the shortest route.

Depth-first search (DFS)

Depth-first means we go as deep as possible down one path before backing up. From the start we pick a neighbor, then a neighbor of that, and keep plunging until we hit a node with no unvisited neighbors. Then we backtrack (step back to the previous node) and try its next unvisited neighbor.

DFS uses a stack instead of a queue. A stack is last-in-first-out (LIFO): the most recently added item comes off first, like a stack of plates where you take the top one. The natural way to write DFS is with recursion, where a function calls itself. Each recursive call is one level deeper into the graph, and Python’s own call stack acts as the stack for us.

def dfs(graph, start, visited=None, order=None):
    if visited is None:        # first call: create fresh containers
        visited = set()
        order = []
    visited.add(start)         # mark on visit
    order.append(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, order)   # go deeper
    return order

print(dfs(graph, "A"))
# -> ['A', 'B', 'D', 'E', 'F', 'C']

Read that order against the graph. From A we descend into B, then B’s first unvisited neighbor D (dead end, backtrack), then E, then F, then from F back up and finally C. DFS commits fully to one branch before exploring another. The numbers on the same graph mark the order each node is reached:

graph TD
    A["A (1)"] --- B["B (2)"]
    B --- D["D (3)"]
    B --- E["E (4)"]
    E --- F["F (5)"]
    A --- C["C (6)"]
    C --- F

If you prefer to avoid recursion, you can use an explicit stack. It produces a valid DFS order too (though possibly a different one, because pushing neighbors reverses the order they come off the stack).

def dfs_iterative(graph, start):
    visited = set()
    order = []
    stack = [start]            # a Python list used as a stack
    while stack:
        node = stack.pop()     # take from the TOP (LIFO)
        if node in visited:
            continue
        visited.add(node)      # mark on POP
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)
    return order

print(dfs_iterative(graph, "A"))
# -> ['A', 'C', 'F', 'E', 'B', 'D']

DFS step-by-step trace

Trace the recursive dfs(graph, "A"). With recursion, the “stack” is the chain of function calls currently open. Each row shows which call is active, the call stack (bottom = A, top = current), and the visited set after the step.

Follow the “visit” rows (steps 1, 2, 3, 5, 6, 10) and you read the order A, B, D, E, F, C. The call stack growing and shrinking is exactly the “go deep, then back up” behavior.

Complexity: why both are O(V + E) time and O(V) space

Both BFS and DFS have the same cost, and the reason is worth understanding rather than memorizing.

Time: O(V + E).

• Each node is added to the visited set once and processed once. That is V units of work.
• For each node we process, we scan its neighbor list. Summed over all nodes, every edge is looked at a fixed number of times (twice in an undirected graph, once from each end). That is proportional to E.
• Total work = V (touch each node) + E (look at each edge) = O(V + E). There is no wasted repetition because the visited set stops us from ever processing a node twice.

Space: O(V).

• The visited set holds at most V nodes.
• The queue (BFS) or stack / recursion depth (DFS) holds at most V nodes in the worst case.
• Both are bounded by the number of nodes, so O(V). (The graph storage itself is O(V + E), but that is the input, not extra space the algorithm creates.)

This is why graph traversal is considered cheap: the cost grows only linearly with the size of the graph.

Traversing a grid

A grid (a 2D layout of cells, like a maze or a screen of pixels) is just a graph in disguise. Each cell is a node; its neighbors are the cells directly up, down, left, and right. You do not need an adjacency list, because you can compute neighbors from the coordinates. BFS on a grid is the standard way to find the shortest path through a maze.

from collections import deque

def shortest_grid_path(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    visited = {start}
    queue = deque([(start, 0)])          # (cell, distance from start)
    while queue:
        (r, c), dist = queue.popleft()
        if (r, c) == goal:
            return dist
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:  # up, down, left, right
            nr, nc = r + dr, c + dc
            in_bounds = 0 <= nr < rows and 0 <= nc < cols
            if in_bounds and grid[nr][nc] == 0 and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append(((nr, nc), dist + 1))
    return -1                            # goal unreachable

maze = [
    [0, 0, 1],
    [1, 0, 1],
    [0, 0, 0],
]   # 0 = open, 1 = wall
print(shortest_grid_path(maze, (0, 0), (2, 2)))
# -> 4

The path is (0,0) → (0,1) → (1,1) → (2,1) → (2,2), four steps. The visited set here holds coordinate tuples instead of letters, but the idea is identical.

When to use which

A short summary: BFS for shortest / nearest, DFS for full exploration and structure. Both cost O(V + E) time; they differ in the order they reveal nodes and in what that order lets you compute.

Common pitfalls

• Forgetting the visited set. On any graph with a cycle, this causes an infinite loop. This is the single most common traversal bug.
• Marking visited on dequeue instead of enqueue (BFS). If you only add a node to visited when you pop it, the same node can be enqueued many times before it is ever popped, wasting memory and, worse, letting duplicate work slip through. Mark a node visited the moment you enqueue it. (In the iterative DFS above we mark on pop and guard with if node in visited: continue, which is the correct pattern for a stack.)
• Using a list as a queue for BFS. list.pop(0) removes from the front but is O(n) because every other element shifts. Over a whole traversal that turns O(V + E) into something much slower. Use collections.deque and popleft, which is O(1).
• Mutable default arguments. In the recursive DFS, the containers are created inside the function with an if visited is None guard. Writing def dfs(graph, start, visited=set()) instead is a classic Python trap: that one set is shared across every call to the function, so a second traversal would still see the first one’s nodes.
• Recursion depth limits. Python caps recursion at about 1000 nested calls by default. On a very deep graph, recursive DFS can raise RecursionError; the iterative stack version avoids this.
• Grid bounds and walls. Always check that a neighbor coordinate is inside the grid before indexing into it, and skip blocked cells, or you will read out of range or walk through walls.

Practice

1. Write a function count_components(graph) that returns how many separate pieces a graph has (a connected component is a group of nodes all reachable from each other). Hint: loop over every node; each time you find an unvisited one, run a traversal from it and count one.
2. Modify the recursive DFS so it also returns the depth at which each node was first visited (the start is depth 0). Compare those depths to the BFS layers from this lesson and note where they differ.
3. Given the maze grid above, change shortest_grid_path to return the actual list of cells on the shortest path, not just its length, using a parent dictionary like the one in shortest_path.