Graph Traversal — BFS and DFS

A graph is just a set of things (nodes, or vertices) and connections between them (edges). Cities and roads, functions and their callers, instruments and their correlations — anything you can draw as dots joined by lines is a graph. Almost every graph question starts by walking the graph: visiting every node reachable from a starting point. There are exactly two disciplined ways to do that walk, and knowing when to use each is the whole game.

Breadth-first search (BFS) explores in rings: first the start node, then everything one step away, then everything two steps away, and so on. It uses a queue (first-in, first-out). Depth-first search (DFS) plunges: follow one edge as far as it goes, hit a dead end, back up, and try the next branch. It uses a stack (last-in, first-out), which recursion gives you for free.

Complexity

Both visit every node once and look at every edge once, so both run in

$$O(V + E),$$

where $V$ is the number of nodes and $E$ the number of edges. Space is $O(V)$ for the visited-set plus the queue or the recursion stack. Neither is "faster" in the big-O sense — they differ in order of visitation, and that order is what you exploit.

Reading the picture

From the diagram, BFS from A visits A → B, C → D, E → F — strictly by distance. DFS from A might visit A → B → D → F → E → C, diving down one branch before exploring the next. Same six nodes, completely different order.

from collections import deque

def bfs(graph, start):
    seen, q, order = {start}, deque([start]), []
    while q:
        node = q.popleft()          # FIFO — this makes it breadth-first
        order.append(node)
        for nbr in graph[node]:
            if nbr not in seen:
                seen.add(nbr)
                q.append(nbr)
    return order

def dfs(graph, node, seen=None, order=None):
    seen = seen or set(); order = order or []
    seen.add(node); order.append(node)
    for nbr in graph[node]:
        if nbr not in seen:
            dfs(graph, nbr, seen, order)   # recursion = the stack
    return order

The only structural difference between the two: BFS pops from the front of a queue, DFS pops from the top of a stack (or recurses). Swap the container and you swap the algorithm.

Where it shows up in quant-dev interviews

Grid problems ("number of islands," "shortest path in a maze") are BFS/DFS in disguise — the grid is a graph where each cell links to its neighbors. On a quant desk the same traversals do real work: resolving a dependency graph of calculations in the right order (topological sort via DFS), finding connected clusters in a correlation network (Markov Chains and correlation-clustering ideas ride on this), and detecting cycles in an order-routing or settlement graph. The interview favorite is "detect a cycle" — DFS with a recursion-stack marker — and its finance cousin, spotting an arbitrage loop, which is the same cycle hunt on a graph of exchange rates.

Master the queue-vs-stack distinction, always guard with a visited set, and remember BFS-for-shortest-hops. That trio answers the large majority of graph questions you'll be handed.