Graph traversal: BFS, DFS and components

Why it matters

Graph traversal sits underneath problems that never mention a graph: a grid of cells, words that differ by one letter, accounts that share an email address, services that depend on each other. Interviewers check three things: whether you can see the graph (what the nodes and edges are), whether you choose the traversal that answers the question, and whether your visited bookkeeping is correct. The same ideas appear in systems work as reachability in dependency graphs, the mark phase of garbage collectors, web crawlers and flooding-based broadcast in networks.

Core ideas

Representation. Adjacency lists suit sparse graphs: O(V + E) space and neighbor iteration proportional to degree. A grid needs no explicit graph; generate the neighbors of (r, c) from a direction array with one bounds check. Estimate V and E before coding: all 4-digit lock states form an implicit graph of 10^4 nodes with 8 neighbors each, small enough to search exhaustively, while many board-game state spaces are not.

BFS. A FIFO queue processes vertices in layers: every vertex at distance d leaves the queue before any vertex at distance d + 1. Invariant: the queue holds at most two consecutive distance values, in non-decreasing order. Because every edge has length 1, the first discovery of a vertex happens along a shortest path, so setting dist[v] = dist[u] + 1 at discovery is final. Mark a vertex visited when you enqueue it, not when you dequeue it; otherwise a vertex can enter the queue once per incoming edge, which inflates time and memory and, if distances are written at enqueue time, can overwrite a correct distance with a larger one.

from collections import deque

def bfs(sources, neighbors):
    dist = {s: 0 for s in sources}      # visited set and distances in one map
    queue = deque(sources)
    while queue:
        u = queue.popleft()
        for v in neighbors(u):
            if v not in dist:           # mark on discovery, not on removal
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist

Multi-source BFS. Seeding the queue with every source at distance 0 gives each vertex its distance to the nearest source in a single O(V + E) pass. It is the same as adding a virtual super-source joined to every real source and subtracting one from the results. A separate BFS per source would cost O(k(V + E)) for k sources.

DFS. DFS follows one path as far as possible, then backtracks; with recursion, the call stack is the stack. It answers reachability and component labeling, and with discovery and finish bookkeeping it detects cycles and produces topological orders (next topic). It does not find shortest paths. Recursive DFS on a 1000 by 1000 grid can reach depth 10^6, far beyond Python's default recursion limit of 1000 and enough to overflow native stacks in other languages, so be able to write the iterative version with an explicit stack.

Components. Loop over all vertices; whenever one is unvisited, start a traversal from it and label everything it reaches. The total is still O(V + E) because each vertex and edge is handled once across all traversals. Counting islands is exactly this on a grid.

Bipartiteness. Two-color with BFS or DFS, giving each neighbor the opposite color; a conflict means an odd cycle. Start a traversal in every component.

Common misconceptions

• "DFS finds shortest paths if I keep the minimum." DFS visits paths in an arbitrary order, and taking minima over all of them is exponential backtracking. Use BFS for unit weights and the shortest-path algorithms for weighted graphs.
• "Marking visited on dequeue is equivalent." At best it wastes work: a vertex can be enqueued once per incoming edge, which multiplies time and memory on grids with many converging paths. At worst, a distance written at enqueue time is overwritten by a longer one. Mark on enqueue.
• "Traversal is O(V) because each vertex is visited once." Every adjacency list is scanned once too, so the bound is O(V + E), which is O(V^2) for dense graphs.
• "One traversal from node 0 covers the graph." Only if the graph is connected. Component counts, bipartite checks and cycle checks must loop over all start vertices.
• "Overwriting the input grid to mark visited is free." It saves memory but destroys the caller's data. Say that you are doing it, or copy, and restore cells when the input must stay intact.

How to approach it

Say the graph out loud before coding: "nodes are cells, edges join 4-neighbors that are both land". Choose the traversal from the question: a minimum number of steps suggests BFS; reachability, grouping or exhaustive exploration suggests DFS or BFS, whichever is simpler to get right. Put neighbor generation in its own function so bounds checks live in one place. Test with an empty grid, a single cell, no land at all, and a disconnected graph. Interviewers at every level expect the O(V + E) analysis; stronger answers also mention recursion depth, the size of an implicit state space, and bidirectional BFS when the branching factor is large, as in word-transformation problems.