14 — Graphs

Recognizing the graph

Most graph questions in the 150 are not presented as graphs. The first skill is seeing one:

Vocabulary:

• Vertex / node — a thing. Edge — a connection.
• Directed — edges have a direction (a → b doesn't imply b → a). Undirected — they go both ways.
• Weighted — edges carry a cost. Unweighted — every edge costs 1.
• Cycle — a path returning to its start. DAG — a directed graph with no cycles.
• Connected component — a maximal group of mutually reachable nodes.

Choosing the traversal

Why BFS finds shortest paths and DFS doesn't

This is the most commonly botched fundamental in graph interviews.

BFS explores in rings: everything 1 step away, then everything 2 steps away, and so on. So the first time BFS reaches a node, it has arrived by a shortest path — nothing shorter was possible, or an earlier ring would have found it.

DFS dives as deep as it can before backing up. It might reach node X after a 50-step detour when a 2-step route existed. Once X is marked visited, the short route never gets to correct it.

    A ─── B ─── C
    │           │
    └─────── D ─┘

BFS from A: reaches D in 1 step (direct edge).
DFS from A: might go A→B→C→D and record 3 steps.

For weighted graphs neither works directly — you need Dijkstra.

Representations

Adjacency list — the default

Store, for each node, a list of its neighbours.

// From an edge list, using a map (works for any node labels)
Map<Integer, List<Integer>> adj = new HashMap<>();
for (int[] e : edges) {
    adj.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
    adj.computeIfAbsent(e[1], k -> new ArrayList<>()).add(e[0]);   // OMIT for a DIGRAPH
}

// When nodes are 0..n-1, arrays are faster and simpler
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }

Whether you add both directions is the single line deciding directed vs. undirected. Say which you're building and why — it's a correctness decision, not a detail.

Why an adjacency list rather than a matrix: a boolean[n][n] matrix costs O(n²) space and O(n) to list a node's neighbours. A list costs O(V + E) space and lists neighbours in O(degree). Real graphs are sparse, so the list wins. Use a matrix only when the graph is dense or you need O(1) "is there an edge between u and v".

Grids — no structure needed

Neighbours are computed:

int[][] DIRS = {{0,1},{0,-1},{1,0},{-1,0}};
for (int[] d : DIRS) {
    int nr = r + d[0], nc = c + d[1];
    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;   // bounds check FIRST
    // ... visit (nr, nc)
}

For an m × n grid: V = m·n, E ≈ 4·m·n, so O(V + E) = O(m · n).

DFS

// Recursive — preferred for readability
private void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
    visited[node] = true;
    for (int next : adj.get(node)) {
        if (!visited[next]) dfs(next, adj, visited);
    }
}

// Iterative — when depth may exceed ~10^4
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
visited[start] = true;
while (!stack.isEmpty()) {
    int node = stack.pop();
    for (int next : adj.get(node)) {
        if (!visited[next]) { visited[next] = true; stack.push(next); }
    }
}

Mark visited when you push/enter, not when you pop. Marking on pop lets the same node be queued many times before it's first processed — still correct, but it can blow up memory on dense graphs.

Grid flood fill

The shape behind Number of Islands, Max Area of Island, and Surrounded Regions.

private int dfs(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') return 0;

    grid[r][c] = '0';                        // "sink" it — doubles as the visited mark
    return 1 + dfs(grid, r + 1, c) + dfs(grid, r - 1, c)
             + dfs(grid, r, c + 1) + dfs(grid, r, c - 1);
}

// caller
int islands = 0;
for (int r = 0; r < rows; r++)
    for (int c = 0; c < cols; c++)
        if (grid[r][c] == '1') { islands++; dfs(grid, r, c); }

How the count works: the outer loops find any unvisited land cell. That's a new island, so increment. Then DFS sinks the entire connected landmass, so those cells are never counted again. Each island is therefore counted exactly once — at whichever of its cells the scan reaches first.

Mutating the input as the visited marker is O(1) space but destructive. Always ask whether that's acceptable; if not, use boolean[m][n]. Asking shows care about side effects.

Crucially: this mark is never undone. Unlike backtracking (15) where restoring is mandatory. Flood fill wants "seen ever"; backtracking wants "on the current path". Getting this backwards is a classic error.

BFS

Queue<Integer> q = new ArrayDeque<>();
boolean[] visited = new boolean[n];
q.offer(start);
visited[start] = true;

int steps = 0;
while (!q.isEmpty()) {
    int size = q.size();                     // one outer iteration == one level
    for (int i = 0; i < size; i++) {
        int node = q.poll();
        if (node == target) return steps;
        for (int next : adj.get(node)) {
            if (!visited[next]) { visited[next] = true; q.offer(next); }
        }
    }
    steps++;
}
return -1;

Same level-size device as tree BFS (12). Use it whenever the answer is a distance or a count of rounds.

Mark visited when enqueuing, not dequeuing. Otherwise a node with three neighbours gets queued three times before it's processed once.

Multi-source BFS

The problem: "how far is each cell from its nearest gate?" Running BFS from every gate separately costs O(gates × m × n).

The trick: seed the queue with all sources at once. The frontier then expands from all of them simultaneously, and the first time it reaches a cell, that's the distance to the closest source. One pass, O(m · n).

Queue<int[]> q = new ArrayDeque<>();
for (int r = 0; r < rows; r++)
    for (int c = 0; c < cols; c++)
        if (grid[r][c] == ROTTEN) q.offer(new int[]{r, c});    // ALL sources seeded

int minutes = 0;
while (!q.isEmpty()) {
    int size = q.size();
    boolean spread = false;
    for (int i = 0; i < size; i++) {
        int[] cell = q.poll();
        for (int[] d : DIRS) {
            int nr = cell[0] + d[0], nc = cell[1] + d[1];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (grid[nr][nc] != FRESH) continue;
            grid[nr][nc] = ROTTEN;
            q.offer(new int[]{nr, nc});
            spread = true;
        }
    }
    if (spread) minutes++;      // only count a minute if something actually changed
}

Rotting Oranges and Walls and Gates are both this. The spread flag prevents counting a final empty round.

Reverse thinking

Pacific Atlantic Water Flow: which cells can drain to both oceans?

• Forward (naive): from each cell, can I reach an ocean? That's O((m·n)²) — a traversal per cell.
• Reverse: start at each ocean and flow uphill, marking every reachable cell. Two traversals, O(m · n). The answer is the intersection.

Surrounded Regions uses the same inversion: rather than testing each region for "is it enclosed?", start from the border and mark everything connected to it as safe. Whatever wasn't marked is enclosed.

The general lesson: when "for each X, can it reach a special place?" is expensive, invert it to "from the special places, what can be reached?" — one traversal instead of n.

Clone Graph

private Map<Node, Node> cloned = new HashMap<>();

public Node cloneGraph(Node node) {
    if (node == null) return null;
    if (cloned.containsKey(node)) return cloned.get(node);      // visited check AND lookup

    Node copy = new Node(node.val);
    cloned.put(node, copy);                                     // REGISTER BEFORE RECURSING
    for (Node nb : node.neighbors) copy.neighbors.add(cloneGraph(nb));
    return copy;
}

Registering before recursing is what terminates on cycles. If A and B are neighbours of each other: cloning A registers A, then recurses to B, which recurses back to A — and finds it already in the map, returning the existing clone instead of recursing forever.

Reverse those two lines and you get infinite recursion on any cyclic graph. Same structure as Copy List With Random Pointer (11).

The map does double duty: clone registry and visited set.

Cycle detection

Undirected — track the parent

private boolean hasCycle(int node, int parent, List<List<Integer>> adj, boolean[] visited) {
    visited[node] = true;
    for (int next : adj.get(node)) {
        if (next == parent) continue;                  // the edge we arrived on — not a cycle
        if (visited[next]) return true;                // reached an already-visited node
        if (hasCycle(next, node, adj, visited)) return true;
    }
    return false;
}

Why the parent check: in an undirected graph every edge appears in both nodes' lists. Walking A → B, node B sees A as a neighbour and A is visited — which looks like a cycle but is just the edge you came in on. Skipping the parent excludes it.

Limitation: with parallel edges (two separate edges between the same pair), next == parent wrongly skips a genuine cycle. You'd need edge IDs. Mention it if multigraphs are allowed. Union-find is often cleaner here anyway.

Directed — the three-colour method

The parent trick fails on digraphs. A node can legitimately be reachable by two different forward paths without any cycle:

    A → B → D
    A → C → D          D visited twice, but NO cycle

You need to distinguish "currently on the recursion stack" (a genuine back-edge → cycle) from "fully explored and finished" (safe).

// 0 = unvisited, 1 = in progress (on the current path), 2 = fully done
private boolean hasCycle(int node, List<List<Integer>> adj, int[] state) {
    if (state[node] == 1) return true;      // back-edge into the current path — CYCLE
    if (state[node] == 2) return false;     // already fully explored — safe

    state[node] = 1;                        // entering
    for (int next : adj.get(node)) {
        if (hasCycle(next, adj, state)) return true;
    }
    state[node] = 2;                        // leaving — fully explored
    return false;
}

Why state 2 matters for complexity, not just correctness. Without it, shared subgraphs get re-explored every time they're reached, which can be exponential. With it, each node is fully explored once: O(V + E).

This is the DFS solution to Course Schedule.

Graph Valid Tree

A graph is a tree iff it's connected and has exactly n − 1 edges.

if (edges.length != n - 1) return false;     // O(1) rejection of most bad inputs
// then verify one traversal reaches all n nodes

Why the edge count check is so powerful: with n nodes, fewer than n − 1 edges must leave the graph disconnected, and more than n − 1 must create a cycle. So after that check passes, verifying either "connected" or "acyclic" is enough — the other follows. That's a real graph-theory argument, and worth stating as one.

Topological sort

An ordering of a DAG where every edge points forward — "do this before that."

Kahn's algorithm (BFS) — preferred

The idea: repeatedly take a node with no remaining prerequisites (indegree 0), output it, and remove its outgoing edges — which may free up more nodes.

int[] indegree = new int[n];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

for (int[] p : prerequisites) {
    adj.get(p[1]).add(p[0]);                 // p[1] must come BEFORE p[0]
    indegree[p[0]]++;                        // p[0] gains a prerequisite
}

Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (indegree[i] == 0) q.offer(i);   // no prerequisites

int[] order = new int[n];
int idx = 0;
while (!q.isEmpty()) {
    int node = q.poll();
    order[idx++] = node;
    for (int next : adj.get(node)) {
        if (--indegree[next] == 0) q.offer(next);   // last prerequisite satisfied
    }
}
return idx == n ? order : new int[0];

idx == n is the cycle check. Nodes inside a cycle can never reach indegree 0 — each waits on another in the cycle — so they're never enqueued. Processing fewer than n nodes proves a cycle exists.

Trace: n = 4, prerequisites [[1,0],[2,0],[3,1],[3,2]] (meaning: to take 1 you need 0, etc.)

Edges: 0→1, 0→2, 1→3, 2→3. Indegrees: [0, 1, 1, 2].

idx == 4 == n → valid order. ✓

Get the edge direction right. [a, b] meaning "to take a you must first take b" is an edge b → a. Reversing it produces a plausible-looking but wrong answer. Restate the direction out loud before coding.

Course Schedule asks "does a valid order exist" (idx == n); Course Schedule II asks "return it" (order). Same code.

DFS variant

Postorder, then reverse. A node finishes only after all its descendants, so reversed finish order is a valid topological order.

private void dfs(int node, List<List<Integer>> adj, int[] state, Deque<Integer> out) {
    state[node] = 1;
    for (int next : adj.get(node)) {
        if (state[next] == 1) throw new IllegalStateException("cycle");
        if (state[next] == 0) dfs(next, adj, state, out);
    }
    state[node] = 2;
    out.push(node);                          // push on FINISH — the stack reverses for you
}

Alien Dictionary is a topological sort over characters — see 18.

Word Ladder — building the graph implicitly

Transform "hit" into "cog" one letter at a time, every intermediate being a real word. Find the shortest chain.

It's unweighted shortest path → BFS. The difficulty is finding neighbours.

Naive: compare every pair of words — O(n² · L). Too slow.

The fix: index words by wildcard patterns. "hot" belongs to buckets "*ot", "h*t", and "ho*". Two words are neighbours exactly when they share a bucket.

Map<String, List<String>> buckets = new HashMap<>();
for (String word : wordList) {
    for (int i = 0; i < word.length(); i++) {
        String pattern = word.substring(0, i) + "*" + word.substring(i + 1);
        buckets.computeIfAbsent(pattern, k -> new ArrayList<>()).add(word);
    }
}
// BFS from beginWord; a node's neighbours are the union of its L wildcard buckets

O(n · L²) preprocessing, then standard level-counting BFS.

The generalizable lesson: when edges are expensive to enumerate, index nodes by a shared key rather than comparing all pairs.

Optimization to mention: bidirectional BFS — search from both ends and stop when the frontiers meet. Roughly square-roots the explored space.

Common bugs

1. Using DFS for a shortest path in an unweighted graph. Use BFS.
2. Marking visited on dequeue instead of enqueue — allows duplicate queue entries.
3. Forgetting the reverse edge on an undirected graph, or adding it on a directed one.
4. Reversing the dependency direction in a topological sort.
5. Not undoing the mark in backtracking, or undoing it in flood fill. Decide which semantics you need.
6. Missing bounds checks before indexing a grid neighbour.
7. Recursing on a 10^5-node graph — StackOverflowError. Go iterative.

Complexity summary

V = vertices, E = edges. For an m × n grid, O(V + E) = O(m · n).