Graph Traversal: A Practical Guide to DFS and BFS

Graph traversal is fundamental to solving many algorithmic problems, and its two core methods are depth-first search (DFS) and breadth-first search (BFS).

Turning the input into a graph

Interview problems rarely hand you the graph itself. The usual input is a node count n and a list of edges such as [[0, 1], [1, 2]]. Your first few lines turn that into an adjacency list, where graph[u] holds every node that u connects to.

def build_graph(n, edges, directed=False):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph

In an undirected graph, such as roads or friendships, an edge from 0 to 1 is also an edge from 1 to 0, and forgetting the second append cuts off part of the graph. A dictionary with keys only for nodes that appear in some edge causes a different bug, a KeyError when a search starts from a node with no edges.

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking.

Recursive Implementation

def dfs_recursive(graph, node, visited):
    visited.add(node)
    print(node)
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

To see the order, run it on this small directed graph.

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

Starting from A, it prints A, B, D, E, F, C. It goes from A into B and then D, which has no neighbors, so it returns to B and tries E, which leads to F. Only then does it return to A for C, whose neighbor F is already visited.

Iterative Implementation

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node)
            stack.extend(reversed(graph[node]))

Two details in the iterative version are easy to get wrong. A stack returns the most recently pushed item first, so without reversed, C comes off before B and the output is A, C, F, B, E, D. That is still depth-first, but it will not match an expected output that visits neighbors in the order they are listed.

The visited check also happens at pop time, so a node can sit on the stack more than once, at most once per edge that leads to it. Marking nodes as they are pushed would change the order on a graph where A points to B and C, and B points to C and D. Recursion visits A, B, C, D, but that stack visits A, B, D, C, because A claimed C before B could reach it. That matters when the answer depends on which node led to which.

Breadth-First Search (BFS)

BFS explores all neighbors before moving to the next level.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

On the same graph, BFS from A prints A, B, C, D, E, F, finishing A's neighbors before anything two edges away. Unlike the iterative DFS, it marks nodes as they enter the queue, for reasons DFS vs BFS explains.

Getting the path back

BFS finds the shortest distance, but many problems ask for the route itself. Record each node's parent when it is first discovered, then walk back from the goal and reverse the list.

from collections import deque

def shortest_path(graph, start, goal):
    parent = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]
        for neighbor in graph[node]:
            if neighbor not in parent:
                parent[neighbor] = node
                queue.append(neighbor)
    return []

The parent dictionary doubles as the visited set. Each node's parent is the node that first reached it, one step closer to the start, so following parents back traces a shortest path.

Grids are graphs too

Many graph problems never use the word graph. In a grid of land and water, a maze, or an image to flood fill, each cell is a node whose neighbors are the passable cells above, below, left, and right, computed from four direction offsets instead of stored in a list.

Number of Islands counts separate groups of land cells. Each time the outer loop reaches land that no earlier search touched, count one island and traverse from there to mark the rest of it, the same loop that counts connected components in DFS vs BFS.

from collections import deque

def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = set()
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != "1" or (r, c) in seen:
                continue
            islands += 1
            seen.add((r, c))
            queue = deque([(r, c)])
            while queue:
                x, y = queue.popleft()
                for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                    if (0 <= nx < rows and 0 <= ny < cols
                            and grid[nx][ny] == "1" and (nx, ny) not in seen):
                        seen.add((nx, ny))
                        queue.append((nx, ny))
    return islands

In Python, grid[-1][c] returns a cell from the bottom row instead of raising an error, so a search that skips the 0 <= half of the bounds check wraps around the top and left edges and ends in a wrong count or a crash.

Spotting a graph problem in disguise

Often the hard part is noticing the graph at all. Ask what the states are and what one move changes. In Open the Lock, four wheels start at 0000, each move turns one wheel by one step, and the lock must never show one of the listed dead ends. Each combination is a node and each turn an edge, so the fewest turns is a shortest path, found by BFS over a graph you never build.

from collections import deque

def open_lock(deadends, target):
    dead = set(deadends)
    if "0000" in dead:
        return -1
    seen = {"0000"}
    queue = deque([("0000", 0)])
    while queue:
        code, turns = queue.popleft()
        if code == target:
            return turns
        for i in range(4):
            digit = int(code[i])
            for step in (1, -1):
                nxt = code[:i] + str((digit + step) % 10) + code[i + 1:]
                if nxt not in seen and nxt not in dead:
                    seen.add(nxt)
                    queue.append((nxt, turns + 1))
    return -1

Phrases like "minimum number of moves" and "is it possible to reach" point to this kind of search. If a cell has to be unmarked after the search leaves it, the problem is backtracking instead, covered in the backtracking guide.

Which one to use

DFS vs BFS covers which one to pick for a given problem, comparing them on shortest paths, cycles, memory, and depth limits. For a routine to practice both, see LeetCode interview tips.