Chapter 7: Graphs

Tree BFS relies on every node having one parent, so each node is enqueued once. In a graph a vertex may be adjacent to many already-seen vertices, and without bookkeeping it is enqueued again from each of them, or forever around a cycle. The visited set fixes this: when $u$ is dequeued, each neighbour $v$ not yet in the set is added to it and enqueued. Marking on enqueue rather than on dequeue matters, because marking late lets $v$ wait in the queue several times at once. Each vertex then enters the queue once and each undirected edge is examined twice, so BFS costs $O(V + E)$ time and $O(V)$ space.

Plain BFS returns vertices in distance order but does not say where one distance ends and the next begins. The previous chapter solved this for trees with the level-size snapshot, and it carries over unchanged: at the start of each round the queue holds exactly the vertices at distance $d$ from the source, so processing exactly len(queue) of them completes level $d$, while the neighbours they discover form level $d + 1$. Alternatively, set dist[v] = dist[u] + 1 when $v$ is first enqueued. Either way every vertex gets its hop distance in $O(V + E)$ time. The visited set is still required, or a vertex reached from two parents would appear in two levels.

A BFS from one source reaches only the vertices joined to it by some path, its connected component. Real graphs are often split: users with no mutual friends, or road networks on separate islands. To visit every vertex, loop over all vertices and start a fresh BFS from each one that is still unvisited, sharing one visited set across all the runs. Each start discovers exactly one new component, so counting starts counts components. The total cost stays $O(V + E)$, because the shared set stops any vertex or edge from being processed twice. Forgetting the outer loop is a common bug that passes connected tests and fails silently otherwise.

The recursive form mirrors the definition: mark the current vertex visited, then call DFS on each neighbour that is not yet visited. When the loop over neighbours ends, the function returns, and that return is the backtracking step, handled automatically by the call stack. Each vertex is marked once and each adjacency list is scanned once, giving $O(V + E)$ time. The recursion depth equals the length of the current path, up to $V$ on a long chain, and Python's default limit of 1,000 frames raises RecursionError on a path graph of a few thousand vertices. The visit order depends on the order of each neighbour list.

Deep graphs overflow the call stack, so production code often replaces recursion with an explicit list used as a stack. Push the start vertex, then repeatedly pop a vertex, skip it if it is already visited, and otherwise mark it and push its unvisited neighbours. A stack is last in, first out, so the neighbour pushed last is explored first, and pushing each neighbour list in reverse reproduces the recursive visit order. Marking happens on pop, not on push: a vertex may be pushed by several neighbours before it is reached, and marking on push still visits everything, but no longer in depth-first order. Time stays $O(V + E)$.

The outer-loop pattern from BFS works identically with DFS: scan the vertices, and whenever one is unlabelled, launch a DFS from it that writes the current component number on every vertex it reaches. Each launch paints one entire component before returning, so the number of launches equals the number of components, and the label array afterwards answers whether $u$ and $v$ are connected in $O(1)$. The total cost is $O(V + E)$, since the shared labels stop any vertex from being painted twice. With $V$ vertices and $E$ edges there are at least $V - E$ components, because each edge merges at most two.

Why is the first arrival shortest? The BFS queue always holds vertices from at most two consecutive distances, $d$ and $d + 1$, with every distance-$d$ vertex ahead of every distance-$(d + 1)$ vertex. Vertices therefore leave the queue in non-decreasing order of distance, and when $v$ is first discovered from $u$, no vertex closer to the source is still waiting to discover it. Setting dist[v] = dist[u] + 1 at that moment is final, so the search can stop as soon as the target is discovered. The argument needs every edge to cost 1; with unequal weights, a path with more edges can be cheaper.

Distances alone do not give directions. To return the route, store parent[v] = u at the moment BFS first discovers $v$ from $u$, the same moment dist[v] is set, which costs only $O(V)$ extra space. The parent pointers form a BFS tree rooted at the source, and every path in that tree is a shortest path. To rebuild the route to a target $t$, follow parent pointers from $t$ back to the source, collecting vertices, then reverse the list. A target that never received a parent, and is not the source, is unreachable. Overwriting a parent after the first discovery breaks this guarantee and can produce a longer path.

Storing a grid's adjacency list would repeat what the coordinates already say, because the neighbours of $(r, c)$ follow from arithmetic. Grid code instead keeps a short list of direction vectors, [(0, 1), (0, -1), (1, 0), (-1, 0)] for 4-connectivity, and computes each neighbour as $(r + dr, c + dc)$. An $m \times n$ grid has $mn$ vertices and fewer than $2mn$ edges, since each cell has at most 4 neighbours and every edge is shared by two cells. Adding the four diagonal vectors gives 8-connectivity, which changes which cells count as touching, and so changes the answer to any region-counting question.

A neighbour computed by arithmetic may not exist. For a cell $(r, c)$ on the top row, $r - 1 = -1$, and in Python grid[-1][c] raises no error: it silently reads the bottom row, so the search wraps around the edge and joins cells that are not adjacent. Every neighbour must pass 0 <= nr < rows and 0 <= nc < cols before it is read, with the check written before the index so short-circuit evaluation protects it. Most problems then add a second filter on the cell's value, such as open versus blocked. Both checks cost $O(1)$ per neighbour and never change the complexity.

With neighbours generated and bounds checked, grid search is ordinary graph search. BFS from a start cell gives the fewest moves to every reachable cell, since each move is one unweighted edge, while DFS is the simpler way to explore a whole connected region. Visited cells can be tracked in a set of (r, c) pairs, in a boolean matrix, or by overwriting the grid itself, which saves $O(mn)$ memory but destroys the input. Both searches take $O(mn)$ time on an $m \times n$ grid. Recursive DFS is risky on large grids: a snake-shaped region of a million cells means a recursion a million frames deep.

Flood fill first reads the original colour of the start cell, because that cell is about to be overwritten. It then recolours the start cell and, recursively or with a queue, visits each 4-neighbour that is in bounds and still has the original colour, recolouring it and continuing from there. A neighbour that has already been recoloured no longer matches, so the new colour acts as the visited set. Only cells in the region and their immediate boundary are examined, so the cost is $O(k)$ for a region of $k$ cells, reaching $O(mn)$ when the whole grid is one colour. Recursive versions can also reach depth $k$.

Using the new colour as the visited mark has one failure case. If the start cell already has the new colour, recolouring changes nothing, so every neighbour of that colour still matches the original, and the fill steps back into cells it has just processed. Recursive DFS bounces between two adjacent cells until Python raises RecursionError, and a BFS re-enqueues them forever. The fix is one line at the top: if the original colour equals the new colour, return the grid unchanged, which is also the correct answer. A separate visited set would prevent the loop as well, at the cost of $O(k)$ extra memory for a region of $k$ cells.

Counting islands is counting connected components, where the vertices are land cells and edges join land cells that share a side. The scan visits cells in row-major order. At an unvisited land cell it has found a new island, since any earlier cell of the same island would already have marked it; it increments the count and runs DFS or BFS to sink the whole island. Each cell is read once by the scan and at most once more by a search, so the cost is $O(mn)$ for $m$ rows and $n$ columns. Diagonal cells do not connect unless the problem says they do, a frequent source of wrong counts.

The search must know which land cells it has already counted. In-place marking overwrites each visited '1' with '0', sinking it, so the grid itself is the visited record and no memory is used beyond the search's stack or queue. The price is that the caller's grid is destroyed, which breaks any code that reuses it and is unsafe when other threads read it. A separate visited set of (r, c) pairs, or a boolean matrix, keeps the input intact at $O(mn)$ extra space, and in Python the boolean matrix is far smaller than a set of tuples. In an interview, ask whether mutating the input is allowed.

The graph is never given; it must be built from the dictionary. Comparing every pair of words for exactly one mismatch costs $O(N^2 L)$ for $N$ words of length $L$: about 6 billion character checks for 50,000 five-letter words. Two faster schemes exist. Wildcard buckets replace each position with * in turn, so hot yields ot, ht, and ho*, and any two words that share a bucket are neighbours; building every bucket costs $O(N L^2)$. Letter substitution tries all 26 letters at each position and keeps candidates found in a hash set of the dictionary, which costs $O(26 L^2)$ per word.

Once neighbours can be generated, the shortest transformation is a BFS from the begin word. Level $k$ holds every word reachable in exactly $k - 1$ changes, so the level at which the end word first appears is the answer, counted in words rather than edges. Remove each word from the dictionary set, or mark it visited, when it is first enqueued; otherwise words that share buckets keep re-enqueueing each other. With letter substitution each dequeued word costs $O(26 L^2)$, including building candidate strings, so BFS runs in $O(26 N L^2)$. Bidirectional BFS, growing from both ends until the frontiers meet, often explores far fewer words.