Graphs: Representations & Traversal Choice

The vocabulary, fast

A graph is a set of nodes (things) connected by edges (relationships). Edges can be directed (one-way: "course A is a prerequisite of B") or undirected (two-way: "A and B are friends"). Almost every graph interview problem starts the same way: the input arrives as an edge list like [[0,1],[1,2]], and your first move is converting it into a usable representation.

Adjacency list: the default representation

An adjacency list stores, for each node, the list of nodes it connects to — like each person keeping their own contact list instead of a giant everyone-by-everyone spreadsheet (that spreadsheet is the adjacency matrix).

from collections import defaultdict

adj = defaultdict(list)
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)     # drop this line for a directed graph

Interview graphs are nearly always sparse (far fewer edges than V²), so the list wins on space and on the operation traversals actually perform — walking neighbors. Reach for the matrix only when you genuinely need O(1) "is this specific edge present" checks on a dense graph.

Grids are graphs you don't have to build

A 2-D grid is an implicit graph: each cell is a node, and its neighbors are the cells up, down, left, and right. No adjacency list needed — generate neighbors from a direction array, and put the bounds check first:

DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def neighbors(r, c, grid):
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
            yield nr, nc

Islands, flood fill, maze distances, rot spreading through oranges — all of these are ordinary graph traversals wearing a grid costume.

BFS vs DFS: same cost, different questions

Both traversals visit every reachable node and edge once — O(V + E) time — so the choice is never about speed. It's about what the visiting order tells you.

Breadth-first search (BFS) explores in expanding rings using a queue: everything 1 step away, then 2, then 3. Because it visits in distance order, the first time BFS reaches a node, it got there by a shortest path (counting edges). That property is the entire reason to pick BFS: "shortest path", "fewest moves", "minimum steps", "nearest" — in an unweighted graph.

from collections import deque

def bfs_distance(start, goal, adj):
    queue = deque([start])
    visited = {start}
    dist = 0
    while queue:
        for _ in range(len(queue)):     # process one full ring
            node = queue.popleft()
            if node == goal:
                return dist
            for nb in adj[node]:
                if nb not in visited:
                    visited.add(nb)     # mark ON ENQUEUE
                    queue.append(nb)
        dist += 1
    return -1

Two details in that template are load-bearing:

1. Mark visited when a node is enqueued, not when it's dequeued. Marked-on-dequeue, a popular node gets appended by several neighbors before its first pop — the queue balloons and the ring structure breaks.
2. The inner for over len(queue) snapshots one ring. That's what lets you count distance in whole levels (or emit per-level output). Skip it when you only need reachability.

Depth-first search (DFS) dives as deep as possible along one path before backing up, via recursion or an explicit stack. Its visiting order says nothing about distance — what it's good at is exhausting connectivity cheaply: what's reachable, how many separate regions exist, does a path exist at all, and computing answers bottom-up as recursion unwinds.

Counting islands is the canonical shape — every unvisited land cell starts a flood fill that consumes its whole island, so the number of times you start is the number of islands:

def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    def fill(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != "1":
            return
        grid[r][c] = "0"                # sink it: acts as visited
        for dr, dc in DIRS:
            fill(r + dr, c + dc)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                fill(r, c)
    return count

On general graphs (which can contain cycles), DFS needs a visited set or it recurses forever — trees are the one place you can skip it. And know how to convert recursion to an explicit stack: deep inputs can overflow the call stack.

Multi-source BFS: spreading from many places at once

"Rot spreads from every rotten orange each minute." "Fill each room with the distance to its nearest gate." These are spreading processes with many starting points, and the trick is delightfully simple: seed all sources into the queue at distance 0 before starting. The wave then expands from every source simultaneously, and the first wave to reach each cell is, by BFS's ordering guarantee, from its nearest source. One traversal answers "distance to the closest source" for the entire grid — running a separate BFS per source would multiply the cost by the number of sources.

Choosing the tool

Pitfalls checklist

1. Visited marked on dequeue instead of enqueue — the classic BFS blow-up.
2. No visited set in graph DFS — infinite loops on any cycle.
3. Bounds check before the array access in grid code, guard clause first.
4. Multi-source problems: all sources go in at distance 0 — not one BFS per source.
5. BFS on weighted edges — its shortest-path guarantee counts edges, not weights.