Graph traversal: BFS and DFS

Searching a list is easy because there is only one way to move. In a graph you must choose a direction at every node, and the choice determines the order in which you see things. There are two canonical strategies: explore broadly with a queue, or dive deeply with a stack. Everything else is a variation.

Pick a starting node and step through both orders on the same graph.

Breadth-first search #

BFS visits every node at distance $k$ before any node at distance $k+1$, so it finds the shortest path in unweighted graphs — measured in number of edges. It uses a queue and records each node's distance when first discovered:

from collections import deque
 
def bfs(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)
                queue.append(neighbour)
    return order

Mark a node as seen when you enqueue it, not when you dequeue it; otherwise a node can be queued several times before it is first processed.

Depth-first search #

DFS follows one branch as far as it goes, then backtracks. It is naturally recursive — the call stack is the stack — or written iteratively with an explicit stack. It is the right tool for:

• detecting cycles,
• topological sorting a directed acyclic graph,
• finding connected components,
• solving mazes and puzzles where any path will do.

def dfs(graph, node, seen=None):
    if seen is None:
        seen = set()
    seen.add(node)
    for neighbour in graph[node]:
        if neighbour not in seen:
            dfs(graph, neighbour, seen)
    return seen

Cost and correctness #

Both run in $O(V + E)$ time: every vertex enters the container once, and every edge is examined once for each endpoint. That is linear in the size of the graph, which is optimal — you cannot do better than looking at the input. The only correctness trap is the cycle: without a visited set, traversal loops forever.

Where next: string matching — searching for a pattern inside a text, with the same halving and re-use ideas in a different guise.