Graph Traversals (BFS, DFS)

A graph is just things and the connections between them: people and friendships, cities and roads, web pages and links, tasks and dependencies. Almost any "how do I reach, explore, or relate these" question is secretly a graph question. And the moment you model it as a graph, you need one skill above all others: how to walk it without getting lost, without going in circles, and without missing anyone. That skill is traversal, and it comes in two flavors that are worth internalizing as two different temperaments.

Breadth-First Search explores in rings. It visits everything one step away, then everything two steps away, and so on, radiating outward like a drop hitting still water. Depth-First Search is the opposite temperament: it commits to a path and plunges as far as it can go, only backing up when it dead-ends. Same graph, same edges, completely different order, and each order unlocks a different set of problems. The one non-negotiable both share is a visited set, because a graph, unlike a tree, can loop back on itself, and without a memory of where you have been, you will circle forever.

BFS explores in rings, and rings mean shortest paths

BFS uses a queue, first in first out, which is exactly what enforces the ring order: you finish draining everyone at distance one before anyone at distance two gets a turn.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()               # oldest first, keeps the rings intact
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)         # mark on enqueue, not on visit
                queue.append(neighbor)
    return order

graph = {1: [2, 3], 2: [1, 4], 3: [1, 5], 4: [2], 5: [3]}
print(bfs(graph, 1))                          # [1, 2, 3, 4, 5]

Note the subtle but important detail: mark a node visited the moment you enqueue it, not when you pop it, or the same node gets queued several times before its first visit. DFS is the same walk with the queue swapped for the call stack: def dfs(node): visited.add(node); for n in graph[node]: if n not in visited: dfs(n). That is the entire difference. Queue gives you rings, recursion gives you plunges.

The same small graph traversed two ways: breadth-first search visits it in rings by distance, node 1, then 2 and 3, then 4 and 5, while depth-first search plunges down one path, 1 to 2 to 4, before backing up to take 3 and 5.

In the wild: degrees of separation

The reason BFS matters far beyond a coding exercise is a property that falls out of the ring order for free: in an unweighted graph, the first time BFS reaches a node, it has reached it by a shortest path. Nothing farther could have arrived sooner, because BFS drains every closer ring first. That single fact is the engine behind "degrees of separation" on a social network, the fewest hops a packet takes across a network, the shortest word ladder from one word to another, and the shortest route through a maze where every step costs the same.

def shortest_hops(graph, start, target):
    visited = {start}
    queue = deque([(start, 0)])               # carry the distance alongside the node
    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist                       # first arrival is guaranteed shortest
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1                                 # target unreachable

This is the same loop as the toy traversal, with one addition: we carry a distance next to each node and return the instant we hit the target. Whether the graph is friendships ("how many introductions to reach this person"), a map of rooms, or a network of routers, it is the identical problem, because BFS does not care what the nodes mean, only that every edge costs the same. That last clause is the fine print. The moment edges have different weights, the ring property breaks and you need Dijkstra, which is BFS with a priority queue.

The trigger

You need to explore a graph, and the shape of the question tells you which walk. "Shortest number of steps," "fewest moves," "closest," or anything level-by-level points to BFS. "Does a path exist," "visit everything," "find connected components," or "detect a cycle" points to DFS. If the data is a network, a grid, or anything you can phrase as nodes and edges, one of these two is almost always the foundation.

Where it shows up

  • Shortest unweighted paths: degrees of separation, word ladders, fewest moves in a puzzle, network hops.
  • Reachability and components: which nodes are connected, how many separate islands exist, flood fill.
  • Cycle detection and ordering: DFS underpins topological sort, deadlock detection, and dependency resolution.

Where it bites

The classic bug is a forgotten or mistimed visited set: forget it entirely and a cyclic graph loops forever; mark on pop instead of on enqueue and you process duplicates. Beyond correctness, the two walks have opposite resource profiles. DFS recursion can overflow the stack on a deep or large graph, so an explicit stack is safer at scale. BFS holds an entire ring in memory at once, which on a wide graph (think millions of neighbors) can balloon the queue. Choosing the wrong walk rarely gives a wrong answer, but it can give you a stack overflow or an out-of-memory where the other would have been fine.

When it is the wrong tool

If edges carry weights, plain BFS no longer finds the shortest path, and you want Dijkstra or, with negative edges, Bellman-Ford. If you have a heuristic for how close you are to the goal, an uninformed sweep wastes effort, and A* will reach the target far faster. And if the "graph" is really a tree with no cycles, you can drop the visited bookkeeping entirely, since there is nothing to loop back into. Reaching for a full graph traversal on structured data that has a cheaper shape is a common bit of over-engineering.

Its neighbors

DFS is literally Backtracking without the undo step, so the two are the same recursion wearing different hats. BFS and DFS are the substrate under Topological Sort, which is a DFS post-order (or a BFS peeling of zero-dependency nodes). Weighted shortest paths generalize BFS into Dijkstra, and Binary Tree Traversals are the special case of all this when the graph happens to be a tree.

References