Breadth-First and Depth-First Search

Almost every graph algorithm is, underneath, a way of visiting every reachable node exactly once. There are two basic orders. Breadth-first search spreads out in rings, finishing everything one hop away before touching anything two hops away. Depth-first search follows one path as far as it goes, then backs up and tries the next branch.

Both cost time in proportion to the nodes plus the edges they reach. They differ in what they discover along the way, and in how much they hold in memory while they do it: a wide frontier for one, a long path for the other. Choosing between them is choosing which of those two costs a given graph can afford.

Visiting Once: The Visited Set

Every traversal keeps a record of the nodes it has already seen and skips any node that comes up again. Without that record, a cycle sends the walk round forever. Even a graph with no cycles at all gets walked again and again wherever paths reconverge, because each route into a shared node re-walks everything beyond it.

The figure shows the effect on a chain of three diamonds, the shape two packages sharing a dependency make. Without a visited set, the first join is reached twice, the second four times and the third eight times: the count doubles at every diamond. A chain of ten diamonds reaches its last node 1,024 times instead of once. With the visited set, each node is expanded once, and the whole traversal costs O(nodes + edges).

The visited set is therefore part of the algorithm's correctness, not a speed-up bolted on. Its key must be a stable identity for the node: a package name and version, a URL after normalization, a state's canonical form. Two keys for the same node reopen the exponential walk.

Breadth-First Search

Breadth-first search, BFS for short, keeps its frontier in a queue, the first-in, first-out structure from Chapter 5. It takes the oldest node from the front, adds that node's unseen neighbours to the back, and repeats. Because every node one hop away enters the queue before any node two hops away, nodes come out in order of their distance from the start, counted in edges.

In the figure, S is taken first and puts A and B in the queue. A and B come out next and add C, D and E. Those three add F, G and H. The colours are the rings: 0, 1, 2 and 3 hops from S. The first time BFS reaches a node, it has reached it by a path with the fewest possible edges, which is the answer to "fewest hops between two routers", "degrees of separation" or "fewest moves to solve this puzzle".

from collections import deque

def bfs(graph, start):
    dist = {start: 0}                 # doubles as the visited set
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist

That short function is all of breadth-first search. A dictionary of distances starts with the start node at zero and doubles as the visited set. A double-ended queue holds the frontier. Each node taken from the front gives every neighbour not yet in the dictionary a distance one greater than its own, and joins the back of the queue. Run on the graph in the figure, it returns 0 for S, 1 for A and B, 2 for C, D and E, and 3 for F, G and H.

Depth-First Search

Depth-first search, DFS, holds the current path on a stack. In the recursive version that stack is the call stack from Chapter 3: each call handles one node and recurses into the first unseen neighbour before looking at the next. It goes as deep as it can, and only when a node has no unseen neighbours left does it return and let its caller try the next branch.

On the same graph, with neighbours tried in alphabetical order, DFS discovers S, A, C, F, D, B, E and G in one long dive. At G every neighbour is already seen, so it backs up through E, B, D and F to C, which still has H unvisited. That single back-up is the dashed curve in the figure. DFS reached G along a path seven edges long, where BFS found one of three.

That is the trade. DFS is poor at distance and good at structure: is there any route at all, is there a cycle, in what order do things finish. The next topic builds a whole algorithm on the order in which DFS finishes nodes.

Finding Cycles

In a directed graph, DFS can mark each node in one of three states: not yet visited, on the current path or finished. Reaching a node that is still on the current path means following an edge back into the path the search is standing on, and that edge closes a cycle. Reaching a finished node is harmless; it only means two routes lead to the same place.

This check is what prints "circular dependency detected" in a build tool or a package manager, and the same test on a graph of which thread waits for which lock is deadlock detection, which Chapter 11 covers. It costs nothing extra: the cycle is found during the same O(nodes + edges) walk.

What Each Holds in Memory

BFS stores its whole frontier, and on a wide graph the frontier is most of the graph. A web crawler is a breadth-first search, and its queue of URLs waiting to be fetched reaches millions of entries. DFS stores one path, which on a narrow graph is short and on a deep graph is long.

Depth is where recursion bites. Measured on CPython 3.15, whose default recursion limit is 1,000 frames, a recursive DFS down a simple chain succeeds at 990 nodes and raises RecursionError at 1,000. Any structure deeper than that, a long linked chain of objects or a dependency chain generated by a tool, needs a DFS that keeps its own stack in a list, where depth is limited by memory rather than by the interpreter.

What a Traversal Costs in Running Systems

The garbage collector's mark phase is a traversal from the program's roots, and Chapter 4 prices it in proportion to the live objects it reaches. "Which services fail if this one does" is a traversal over reversed call edges. A crawler is BFS with a politeness delay per site. All of them cost O(nodes + edges).

In real graphs the edges usually dominate that sum. One account with a million followers is a million steps on its own, whatever the size of the rest of the graph. A traversal that visits a few high-degree nodes can cost more than one that visits thousands of ordinary ones, which is where the time goes when a "simple" graph walk takes seconds.