Graphs: every variation

A graph is a set of nodes and a set of edges between them. That much is easy. The hard part is that most graph problems in an interview are not presented as graphs. They arrive as a grid of characters, a list of course prerequisites, a set of division equations, a ladder of words, a pile of email accounts to merge, or a lock with four dials. None of those statements contain the word “graph”. The work is to see the graph, name its parts, and choose a representation. Once the graph is built, the algorithm is almost always one of five standard ones, and you already know all five.

So the load-bearing sentence for this whole chapter is: name the nodes, name the edges, then pick the algorithm. Candidates fail at the first two steps, not the third. A person who can say “a node is a cell, an edge joins two cells that share a side” has already solved Number of Islands; a person who jumps straight to writing a queue has not, and will spend the round patching bounds checks.

The second organising idea is the choice rule, and it is short. Use BFS when you need the fewest edges on an unweighted graph, because BFS visits nodes in order of distance from the source. Use DFS when you need to explore a whole component, detect a cycle, or build an ordering. Use Dijkstra when edges carry non-negative weights. Use topological sort when the graph is a DAG and the question is about ordering or dependency. Use union-find when the question is about connectivity and the edges arrive over time.

Recognising it from the phrasing

The interviewer says	They mean	Algorithm	Answer is
“shortest path”, unweighted	fewest edges	BFS from the source	the level count
“shortest path”, weighted, non-negative	cheapest path	Dijkstra with a heap	`dist[target]`
“number of islands / regions / connected components”	count the components	DFS or BFS flood fill, or union-find	a counter, or `dsu.components`
“course schedule / build order / dependency”	a valid ordering	topological sort, Kahn or DFS	the order list
“can these be merged / are these the same group / accounts, equations”	dynamic connectivity	union-find	the roots, grouped
“detect a cycle”, directed	a back edge exists	DFS with three colours, or Kahn’s leftover count	a boolean
“detect a cycle”, undirected	a repeated meeting	DFS tracking the parent, or union-find	a boolean
“rotting oranges / spread over time / minimum steps for all”	simultaneous spread	multi-source BFS	the last level index
“clone / copy a graph”	a structural copy	DFS with an old-node-to-new-node map	the copy of the entry node

Before writing any code, ask two questions out loud: what is a node, and what is an edge? In a grid the node is a cell (r, c) and the edges join it to its four neighbours. In course scheduling the node is a course and the edge points from a prerequisite to the course that needs it. In the equations problem the node is a variable and the edge carries a ratio, so the path product is the answer. In Open the Lock the node is a four-digit string, which is not a physical thing at all, and the edge is one turn of one dial. Saying this out loud is worth real points, because it is the step that separates the people who recognise a graph from the people who memorised BFS. It also fixes the representation for you: if the nodes are 0..n-1 use a list of lists, and if the nodes are labels use a dict.

The templates

Six templates. The first builds the graph, and the other five are the algorithms. Templates 2 and 3 share a skeleton — a container, a visited set, a pop, a neighbour loop — and differ only in whether the container is a queue or a stack. That single change is the whole difference between “shortest” and “reachable”, so learn the skeleton once.

Template 1 — build an adjacency list from an edge list. Use when the input is a list of pairs.

def build_graph(n, edges, directed=False):
    adj = {i: [] for i in range(n)}              ## every node exists, even isolated ones
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)                     ## the ONE line that differs
    return adj

def build_graph_labelled(edges, directed=False):
    adj = {}                                     ## nodes are arbitrary labels, not 0..n-1
    for u, v in edges:
        adj.setdefault(u, []).append(v)
        adj.setdefault(v, [])                    ## make sure v exists as a key
        if not directed:
            adj[v].append(u)
    return adj

## tests

assert build_graph(3, [(0, 1), (1, 2)]) == {0: [1], 1: [0, 2], 2: [1]}
assert build_graph(3, [(0, 1), (1, 2)], directed=True) == {0: [1], 1: [2], 2: []}
assert build_graph(2, []) == {0: [], 1: []}
assert build_graph_labelled([("a", "b")], directed=True) == {"a": ["b"], "b": []}
print(build_graph(3, [(0, 1), (1, 2)]))

{0: [1], 1: [0, 2], 2: [1]}

Template 2 — BFS for the fewest edges. Use when the graph is unweighted and the question asks for a minimum number of steps. The answer is recorded as the level counter, which increases once per snapshot of the queue.

from collections import deque

def bfs_shortest_edges(adj, source, target):
    if source == target:
        return 0
    visited = {source}                           ## mark ON PUSH, never on pop
    queue = deque([source])
    steps = 0
    while queue:
        steps += 1
        for _ in range(len(queue)):              ## the level snapshot: one whole layer
            node = queue.popleft()
            for nxt in adj[node]:
                if nxt in visited:
                    continue
                if nxt == target:
                    return steps
                visited.add(nxt)
                queue.append(nxt)
    return -1

## tests

adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
assert bfs_shortest_edges(adj, 0, 4) == 3
assert bfs_shortest_edges(adj, 0, 3) == 2
assert bfs_shortest_edges(adj, 0, 0) == 0
assert bfs_shortest_edges({0: [], 1: []}, 0, 1) == -1
print(bfs_shortest_edges(adj, 0, 4))

Template 3 — DFS, recursive and iterative. Use when you must visit a whole component. The recursive form is shorter, but Python’s recursion limit is about 1000 frames and a path of 200000 cells will crash it, so the iterative form is the one to write for large inputs. Note the difference in where you mark: the recursive form marks on entry, and the iterative form marks on pop, because a node can be pushed onto the stack several times before it is popped.

def dfs_recursive(adj, source, visited=None):
    if visited is None:
        visited = set()
    visited.add(source)                          ## mark on ENTRY
    for nxt in adj[source]:
        if nxt not in visited:
            dfs_recursive(adj, nxt, visited)
    return visited

def dfs_iterative(adj, source):
    visited = set()
    stack = [source]
    while stack:
        node = stack.pop()
        if node in visited:                      ## a node can be pushed many times
            continue
        visited.add(node)                        ## mark on POP, not on push
        for nxt in adj[node]:
            if nxt not in visited:
                stack.append(nxt)
    return visited

## tests

adj = {0: [1], 1: [0, 2], 2: [1], 3: []}
assert dfs_recursive(adj, 0) == {0, 1, 2}
assert dfs_iterative(adj, 0) == {0, 1, 2}
assert dfs_iterative(adj, 3) == {3}
chain = {i: ([i + 1] if i + 1 < 100000 else []) for i in range(100000)}
assert len(dfs_iterative(chain, 0)) == 100000    ## recursion would blow the stack here
print(sorted(dfs_recursive(adj, 0)), len(dfs_iterative(chain, 0)))

[0, 1, 2] 100000

Template 4 — topological sort by Kahn’s algorithm. Use when the graph is a DAG and the question is about ordering. The answer is the order list. The same run also answers “is there a cycle”: if the order is shorter than n, the leftover nodes all have a remaining in-degree, so each of them waits on another leftover node, and that is a cycle. One algorithm, two questions.

from collections import deque

def topological_order(n, edges):
    adj = {i: [] for i in range(n)}
    indegree = [0] * n
    for u, v in edges:                           ## edge u -> v means u comes first
        adj[u].append(v)
        indegree[v] += 1
    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in adj[node]:
            indegree[nxt] -= 1                   ## remove the edge, not the node
            if indegree[nxt] == 0:
                queue.append(nxt)
    if len(order) < n:                           ## leftover nodes sit on a cycle
        return []
    return order

## tests

assert topological_order(4, [(0, 1), (1, 2), (2, 3)]) == [0, 1, 2, 3]
assert topological_order(2, [(0, 1), (1, 0)]) == []
assert topological_order(3, []) == [0, 1, 2]
assert len(topological_order(4, [(0, 1), (0, 2), (1, 3), (2, 3)])) == 4
print(topological_order(4, [(0, 1), (0, 2), (1, 3), (2, 3)]), topological_order(2, [(0, 1), (1, 0)]))

[0, 1, 2, 3] []

Template 5 — Dijkstra with a heap. Use when edges have non-negative weights. The answer is the dist array. The line if d > dist[u]: continue is the whole trick of the practical version. A textbook Dijkstra decreases a key inside the heap, but Python’s heapq has no decrease-key operation. So instead you push a second, cheaper entry for the same node and leave the old one in place. When the stale entry surfaces later, its recorded distance d is worse than the dist[u] you have already settled, so you skip it. The heap grows to $O (E)$ entries rather than $O (V)$ , which changes nothing about the $O (E lo g V)$ bound because $lo g E$ and $lo g V$ differ by a constant factor.

import heapq

def dijkstra(n, weighted_edges, source):
    adj = {i: [] for i in range(n)}
    for u, v, w in weighted_edges:               ## directed; add the reverse for undirected
        adj[u].append((v, w))
    dist = [float("inf")] * n
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:                          ## a stale copy of u: skip it
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))   ## push a new entry, never decrease a key
    return dist

## tests

edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5)]
assert dijkstra(4, edges, 0) == [0, 3, 1, 4]
assert dijkstra(2, [], 0) == [0, float("inf")]
assert dijkstra(3, [(0, 1, 7), (1, 2, 2)], 0) == [0, 7, 9]
print(dijkstra(4, edges, 0))

[0, 3, 1, 4]

Template 6 — union-find with path compression and union by size. Use when the question is about connectivity and the edges arrive one at a time. The answer is either find(a) == find(b), or the components counter, or the return value of union — False means the two ends were already joined, which is how you detect a redundant edge. With both optimisations the amortised cost per operation is $O (α (n))$ , the inverse Ackermann function, which is below 5 for any n you can store. That is not constant, but it is near-constant, and saying it that way is more accurate than saying $O (1)$ .

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   ## path compression, halving form
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                         ## already joined: this edge is redundant
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra                      ## union by size: small tree under big tree
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

## tests

dsu = DSU(5)
assert dsu.union(0, 1) is True
assert dsu.union(1, 2) is True
assert dsu.union(0, 2) is False
assert dsu.find(2) == dsu.find(0)
assert dsu.components == 3
print(dsu.components, dsu.find(0) == dsu.find(2), dsu.union(0, 2))

3 True False

The grid as a graph

A grid is the single most common disguise, so treat it as the default case rather than a special one. The node is the pair (r, c). The edges join a cell to its four orthogonal neighbours, and you generate them with a fixed direction list rather than four copied blocks of code:

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

Then every traversal has the same three-line inner loop: add the offsets, check the bounds, check the cell is the kind you can enter. The bounds check 0 <= nr < rows and 0 <= nc < cols must come first, because Python’s negative indexing means grid[-1][c] is a legal read of the last row and will silently wrap your search around the board. Eight-way movement is the same loop with an eight-entry direction list, so nothing else changes.

There are two ways to mark a cell visited, and you should state your choice aloud. A visited set of (r, c) pairs costs $O (rc)$ extra space and leaves the input untouched. Mutating the grid — writing a 0 over an island cell, or a 2 over a fresh orange — costs $O (1)$ extra space and is faster, but it destroys the caller’s data. Say “I am going to mutate the input as my visited marker, which is $O (1)$ space; tell me if the grid must be preserved and I will use a set instead”. Doing it silently is the version that costs you the round.

Multi-source BFS is the trick people miss. When the question is “how long until everything is reached”, the naive plan is to run one BFS from each source and take the minimum, which costs $O (S \cdot rc)$ . Instead, push every source into the queue before the first pop. The queue then holds all distance-0 nodes, then all distance-1 nodes, and so on, exactly as it would for one source. Because the queue is still non-decreasing in distance, the first time BFS reaches any cell, it has reached it by the shortest route from the nearest source. One pass, $O (rc)$ .

Worked example — rotting oranges. The grid is [[2,1,1],[1,1,0],[0,1,1]], where 2 is rotten, 1 is fresh and 0 is empty. There is one rotten orange, at (0,0). Minute 1 rots (0,1) and (1,0). Minute 2 rots (0,2) and (1,1). Minute 3 rots (2,1). Minute 4 rots (2,2). No fresh orange is left, so the answer is 4. The loop runs one level per minute, and it stops as soon as fresh reaches zero so that a final empty level does not add a phantom minute. If any fresh orange is unreachable, fresh stays positive and the answer is -1.

from collections import deque

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

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))             ## SEED EVERY SOURCE before the first pop
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:
        minutes += 1
        for _ in range(len(queue)):              ## one whole minute per level
            r, c = queue.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2             ## mutate the grid as the visited mark
                    fresh -= 1
                    queue.append((nr, nc))
    return -1 if fresh > 0 else minutes

## tests

assert oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]) == 4
assert oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]) == -1
assert oranges_rotting([[0, 2]]) == 0
assert oranges_rotting([[2, 2], [1, 1]]) == 1
print(oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))

The problems

P1. Number of islands, by DFS — count the connected groups of “1” cells in a character grid

Which template. Template 3, the iterative DFS, run once per unvisited land cell. The trick. The outer double loop is not a search; it is a hunt for a component that has not been seen yet. Each time it finds one, the counter goes up by one and the inner DFS erases the whole component so it is never counted again. That separation — outer loop counts, inner loop consumes — is the shape of every connected-components problem.

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

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    seen = set()
    islands = 0
    for r0 in range(rows):
        for c0 in range(cols):
            if grid[r0][c0] != "1" or (r0, c0) in seen:
                continue
            islands += 1                         ## one new component starts here
            stack = [(r0, c0)]
            seen.add((r0, c0))
            while stack:                         ## iterative DFS: no recursion limit
                r, c = stack.pop()
                for dr, dc in DIRS:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1" \
                            and (nr, nc) not in seen:
                        seen.add((nr, nc))       ## mark on PUSH to avoid duplicates
                        stack.append((nr, nc))
    return islands

## tests

g1 = [["1", "1", "0"], ["1", "0", "0"], ["0", "0", "1"]]
assert num_islands(g1) == 2
assert num_islands([["1", "1"], ["1", "1"]]) == 1
assert num_islands([["0", "0"], ["0", "0"]]) == 0
assert num_islands([]) == 0
print(num_islands(g1))

Complexity. $O (rc)$ time and $O (rc)$ space for the visited set and the stack.

P2. Number of islands, by union-find — the same count, with the components merged instead of walked

Which template. Template 6. The trick. Give every cell the index r * cols + c so the grid becomes a flat array of rows * cols nodes. Then union each land cell with its neighbour above and its neighbour to the left only. Those two directions are enough, because by the time you reach a cell the cells below and to the right have not been processed, and every adjacency is therefore visited exactly once. The count starts at rows * cols, so subtract the water cells, which were never merged with anything. Compare this against P1 out loud: DFS is simpler here and union-find is the answer they want when islands are added one at a time and the count must be re-reported after each addition.

class DSU:
    def __init__(self, n):
        self.parent, self.size, self.components = list(range(n)), [1] * n, n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb], self.size[ra] = ra, self.size[ra] + self.size[rb]
        self.components -= 1
        return True

def num_islands_dsu(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    dsu = DSU(rows * cols)
    water = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != "1":
                water += 1                       ## water cells are components too: subtract them
                continue
            for dr, dc in ((-1, 0), (0, -1)):    ## up and left only: every edge seen once
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
                    dsu.union(r * cols + c, nr * cols + nc)
    return dsu.components - water

## tests

g1 = [["1", "1", "0"], ["1", "0", "0"], ["0", "0", "1"]]
assert num_islands_dsu(g1) == 2
assert num_islands_dsu([["1", "1"], ["1", "1"]]) == 1
assert num_islands_dsu([["0", "0"], ["0", "0"]]) == 0
assert num_islands_dsu([["1", "0", "1"]]) == 2
print(num_islands_dsu(g1), num_islands_dsu([["1", "0", "1"]]))

2 2

Complexity. $O (rc \cdot α (rc))$ time, $O (rc)$ space.

P3. Max area of island — the size of the largest connected group of 1 cells

Which template. Template 3, with a counter instead of a flag. The trick. Sink each cell as you push it, not as you pop it. If you sink on pop, a cell reachable from two different neighbours gets pushed twice, popped twice, and counted twice, and the area comes out too large on any island that is not a straight line. Counting on pop and marking on push is the pairing that makes each cell contribute exactly once.

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

def max_area_of_island(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    best = 0
    for r0 in range(rows):
        for c0 in range(cols):
            if grid[r0][c0] != 1:
                continue
            area = 0
            stack = [(r0, c0)]
            grid[r0][c0] = 0                     ## sink it: the grid IS the visited set
            while stack:
                r, c = stack.pop()
                area += 1                        ## count on POP, exactly once per cell
                for dr, dc in DIRS:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 0         ## sink on PUSH, not on pop
                        stack.append((nr, nc))
            best = max(best, area)
    return best

## tests

g = [[1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1]]
assert max_area_of_island(g) == 3
assert max_area_of_island([[0, 0], [0, 0]]) == 0
assert max_area_of_island([[1, 1], [1, 1]]) == 4
assert max_area_of_island([]) == 0
print(max_area_of_island([[1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1]]))

Complexity. $O (rc)$ time, $O (rc)$ space for the stack in the worst case.

P4. Flood fill — recolour the region connected to a starting pixel

Which template. Template 3 on a grid, with the colour test in place of a visited set. The trick. The guard if old_colour == new_colour: return image is the entire problem. Without it, recolouring a pixel to the colour it already has leaves the entry test true forever, so the same cells are pushed again and again and the loop never ends. Interviewers include that case deliberately.

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

def flood_fill(image, sr, sc, new_colour):
    old_colour = image[sr][sc]
    if old_colour == new_colour:
        return image                             ## without this guard the loop never ends
    rows, cols = len(image), len(image[0])
    stack = [(sr, sc)]
    image[sr][sc] = new_colour
    while stack:
        r, c = stack.pop()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old_colour:
                image[nr][nc] = new_colour       ## recolouring is the visited mark
                stack.append((nr, nc))
    return image

## tests

assert flood_fill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2) == [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
assert flood_fill([[0, 0], [0, 0]], 0, 0, 0) == [[0, 0], [0, 0]]
assert flood_fill([[1, 2], [3, 4]], 0, 0, 9) == [[9, 2], [3, 4]]
print(flood_fill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2))

[[2, 2, 2], [2, 2, 0], [2, 0, 1]]