Graphs: The Core Idea

A graph problem is any problem about relationships between things, where the relationships — not the things — are what you reason over. People and friendships. Cities and flights. Courses and prerequisites. Cells of a map and the cells next to them. If the input is a list of pairs, you are probably holding a graph.

This is the largest section in the course, and it is worth the time. Graphs absorb more interview questions than any pattern except trees, and unlike trees they arrive in disguise: a grid of "1" and "0", a list of words, a set of email accounts.

Start with the simplest question: can I get from A to B? The naive answer is to try every path. In a graph of 12 nodes where every node connects to every other, there are about 9.9 million simple paths from A to B; with 15 nodes, about 17 billion. The repair is the idea this whole section rests on: visit each node once, and remember that you did. With a visited set, the same question costs O(V + E) — for 15 nodes and 100 edges, about 115 steps.

The picture before the code

The chalk is the visited set. The list of junctions still to explore is the frontier. The only real choice is what kind of list the frontier is. Take the newest junction first (a stack) and you go deep down one corridor before trying others: that is depth-first search, DFS. Take the oldest first (a queue) and you spread out in rings — every junction one step away, then every junction two steps away: that is breadth-first search, BFS.

How to recognise it

Five signals in the problem statement:

• Things with connections. The input is a list of pairs: [[0, 1], [1, 2]], [course, prerequisite], [from, to, time]. A list of pairs is an edge list, and an edge list is a graph.
• Reachability. "Can I get from A to B?" "Which cells can reach the ocean?" "Is everyone connected?"
• A grid with neighbours. This is the disguise that catches most people. Each cell is a node, joined to the cells above, below, left and right. Islands, mazes, flood fill, rotting fruit — graph problems wearing a matrix costume.
• Dependencies and ordering. "In what order can I take these courses?" "Can this build finish?" That is topological sort, and it detects impossible requirements for free.
• Grouping. "How many separate clusters?" "Which accounts belong to the same person?" That is connected components, or Union-Find.

The constraints confirm it. With V and E up to about 10^5, the intended cost is O(V + E) for a traversal or O(E log V) for weighted shortest paths. If your plan is worse than that, you either have a bug or the wrong algorithm.

Representing a graph

Interviewers rarely hand you a graph. They hand you an edge list like [[0, 1], [1, 2], [2, 0]]. It is compact but useless for walking: "who are node 1's neighbours?" means scanning every edge. So step one of nearly every graph problem is to build an adjacency list — for each node, the list of its neighbours.

1def build_graph(n: int, edges: list[list[int]], directed: bool = False) -> list[list[int]]:2    """Turn an edge list into an adjacency list for nodes 0..n-1."""3    graph: list[list[int]] = [[] for _ in range(n)]4    for u, v in edges:5        graph[u].append(v)6        if not directed:7            graph[v].append(u)                   # undirected: both directions8    return graph

Building costs O(V + E) time and space. The if not directed line is the most consequential line in graph code: a friendship goes both ways, a prerequisite does not.

There are two other shapes. An adjacency matrix is a V × V grid where matrix[u][v] is 1 when the edge exists. A neighbour function builds nothing at all: it computes the neighbours when asked. A grid cell's neighbours are the four cells around it; a word's neighbours in a word ladder are the words one letter away.

Default to the adjacency list. Real graphs are sparse: a matrix for 10^5 nodes needs 10^10 cells, which does not fit in memory at all.

How it works: the visited invariant

Every traversal keeps one promise: a node enters the frontier at most once, because it is marked visited the moment it is discovered. From that promise, the cost follows. Each node is pushed and popped once: O(V). Each node's neighbour list is read once when it is popped, so the total reading is the sum of all list lengths: O(E) (2E for undirected graphs, since each edge is stored twice). Together, O(V + E).

BFS keeps a second promise. The queue always holds nodes in order of distance from the start, and never spans more than two neighbouring distances — all the nodes at distance d before any at distance d + 1. So the first time BFS reaches a node, it has reached it by a shortest path (counting edges). This is a guarantee, not a tendency. DFS gives no such guarantee: it may reach the target down a winding 40-edge corridor while a 3-edge path exists.

The templates

DFS, recursive and iterative. The recursive form is shortest to write. The iterative form avoids Python's recursion limit — about 1,000 frames by default, which a 5,000-node chain exceeds.

1def dfs_recursive(graph: list[list[int]], node: int, visited: set[int]) -> None:2    """Visit everything reachable from node."""3    visited.add(node)                            # mark on entry4    for nxt in graph[node]:5        if nxt not in visited:6            dfs_recursive(graph, nxt, visited)789def dfs_iterative(graph: list[list[int]], start: int) -> set[int]:10    """Same reach as the recursive DFS, without the recursion limit."""11    visited = {start}12    stack = [start]13    while stack:14        node = stack.pop()15        for nxt in graph[node]:16            if nxt not in visited:17                visited.add(nxt)                 # mark when pushed18                stack.append(nxt)19    return visited

BFS with distances. Swap the stack for a deque and pop from the left. Storing the distance in a dict does double duty: a node is visited exactly when it has a distance.

1from collections import deque234def bfs_distances(graph: list[list[int]], start: int) -> dict[int, int]:5    """Fewest edges from start to every reachable node."""6    dist = {start: 0}7    queue = deque([start])8    while queue:9        node = queue.popleft()10        for nxt in graph[node]:11            if nxt not in dist:                  # dist doubles as the visited set12                dist[nxt] = dist[node] + 113                queue.append(nxt)14    return dist151617def count_components(n: int, edges: list[list[int]]) -> int:18    """Outer loop: every node not yet seen starts a new component."""19    graph = build_graph(n, edges)20    visited: set[int] = set()21    count = 022    for node in range(n):23        if node not in visited:24            count += 125            visited |= dfs_iterative(graph, node)26    return count

Line by line, the parts that matter:

• The mark comes with the discovery, not with the processing. In dfs_iterative and bfs_distances, a node is added to visited or dist in the same step that pushes it. That is what keeps each node in the frontier at most once.
• count_components has an outer loop. One traversal only reaches one component. Looping over every node and starting a new traversal from each unvisited one covers them all — and counts them.
• A grid needs only a neighbour function. Everything else stays the same:

1DIRECTIONS = ((-1, 0), (1, 0), (0, -1), (0, 1))234def grid_neighbours(rows: int, cols: int, r: int, c: int):5    """Yield the in-bounds up/down/left/right neighbours of (r, c)."""6    for dr, dc in DIRECTIONS:7        nr, nc = r + dr, c + dc8        if 0 <= nr < rows and 0 <= nc < cols:9            yield nr, nc

The forms it takes

The traversal barely changes across this section. What changes is the question and the bookkeeping:

Complexity

For a grid, V = m × n and E is about 4 × m × n, so a traversal is O(m × n). A 1,000 × 1,000 grid is a million nodes; counting its islands took about half a second in Python.

Where it goes wrong

Five failure modes. The first gives right answers far too slowly; the others give wrong answers with no error.

• Marking visited when a node is popped, not when it is pushed. Before its turn comes, a node can be pushed once for every edge that points at it. On a 1,000-node graph where every node connects to every other, BFS that marks on push makes 1,000 pushes. Marking on pop makes 499,501. If the code also forgets to skip an already-visited node when it pops it, every duplicate is expanded again: about 499 million neighbour checks instead of 999,000.
• Grid bounds. In Python, grid[-1][0] does not raise — it reads the last row. A flood fill that skips the bounds check leaks from the top edge into the bottom, and the count is wrong with no error.
• Edge direction. Adding the reverse edge to a prerequisite graph makes every dependency mutual, so every pair looks like a cycle. Leaving it out of a friendship graph makes half the graph unreachable. Read the statement for the word that describes the edge — "requires" is directed, "connected to" is not — and ask if it is unclear.
• Only one component traversed. A traversal from node 0 reaches only node 0's component. Always test with an isolated node, one with no edges.
• The wrong algorithm for the weights. BFS on a weighted graph returns the fewest edges, not the lowest cost. Dijkstra on a graph with negative weights returns a confident wrong answer. (The reverse, Dijkstra where every edge costs the same, is correct but pays a log factor for nothing.) Before writing shortest-path code, ask: are edges weighted, and can a weight be negative?