Graph Traversal: BFS & DFS

Graph traversal is the act of visiting every reachable node in a graph exactly once. Two algorithms dominate: Breadth-First Search (BFS) and Depth-First Search (DFS). They ask the same question — “which node should I visit next?” — and answer it differently.

The intuition

Drop a stone in still water. The ripples spread outward in rings, reaching everything one edge-hop away before anything two hops away. That is BFS. Every node at distance d is visited before any node at distance d + 1.

Now imagine following a hiking trail. You pick one path and walk until you hit a dead end. Only then do you backtrack to the last fork and try the next branch. That is DFS. You commit to one direction until you cannot go further, then unwind.

Both strategies visit every reachable node. They differ in order — and that difference determines which problems each solves well.

Try it

Pick a start node, choose BFS, DFS, or both side by side, then step through or let it play. Watch the queue grow and shrink for BFS; watch the stack lurch forward and pop back for DFS. Notice how BFS visits nodes in concentric rings while DFS dives straight to a leaf before returning.

Breadth-First Search

The queue

BFS uses a FIFO queue. You enqueue the start node, then loop: dequeue the front, mark it visited, enqueue all unvisited neighbors. Because neighbors are added to the back and processed from the front, every node at the current distance is drained before any node one hop further is touched.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []

    while queue:
        node = queue.popleft()       # dequeue from front
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor) # enqueue at back

    return order

Shortest paths in unweighted graphs

BFS’s level-by-level expansion is exactly what “shortest path” means in an unweighted graph: fewest edges. The first time BFS reaches a node, it has done so via the shortest possible route. No relaxation or priority queue is needed — the queue ordering guarantees it.

This breaks down the moment edges have weights. For weighted graphs you need Dijkstra or Bellman-Ford. BFS only counts hops, not costs.

Complexity

BFS visits every vertex once and follows every edge once in each direction: O(V + E) time and O(V) space for the visited set and queue.

Depth-First Search

The stack

DFS uses a LIFO stack — either an explicit one or the call stack via recursion. You push the start node, then loop: pop the top, mark it visited, push all unvisited neighbors. Because neighbors are pushed to the top and immediately available for the next iteration, DFS always extends the current path rather than broadening it.

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []

    while stack:
        node = stack.pop()           # pop from top
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in reversed(graph[node]):  # reverse for consistent order
            if neighbor not in visited:
                stack.append(neighbor)

    return order

def dfs_recursive(graph, node, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []
    visited.add(node)
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)
    return order

What DFS is good for

• Cycle detection: in a directed graph, if DFS encounters a node already in the current recursion stack, you have a cycle. In an undirected graph, any already-visited neighbor (other than the node you came from) indicates a cycle.
• Topological sort: for directed acyclic graphs (DAGs), reverse the DFS finish order to get a valid topological ordering.
• Connected components: run DFS from each unvisited node; each run covers one component.
• Maze and path existence: DFS answers “does a path exist?” naturally by following branches to completion.

Complexity

Same as BFS: O(V + E) time and O(V) space. The only practical difference is stack depth — recursive DFS can hit Python’s recursion limit on very deep graphs; iterative DFS avoids this.

The visited set

BFS vs DFS at a glance

Neither is universally better. BFS wins when you need the closest answer first. DFS wins when you need to fully explore a branch, detect cycles, or produce an ordering.

Live: BFS returning shortest distances

This runnable example builds a small adjacency dict, runs BFS from node 0, and prints the shortest unweighted distance from 0 to every other node.

Where these show up

• Web crawling: BFS from a seed URL discovers all pages reachable within k hops before going deeper — good for breadth-first indexing.
• Dependency resolution: package managers use DFS-based topological sort to determine install order (all dependencies before the dependent).
• Connected components: label every node in a social graph or network cluster by running BFS/DFS until all nodes are colored.
• Grid and maze search: treat each cell as a node, its passable neighbors as edges. BFS finds the shortest path in an unweighted grid; DFS answers reachability.

Quick check