readyforhires
Sign up free

Graphs 101

Intermediate · 4 chapters · 8 min read · Model the problem as nodes and edges, then let BFS, DFS or Dijkstra do the work.

Practise this in the app All guides

Recognising a graph problem

Nodes and edges everywhere

A graph is a set of nodes connected by edges. Edges can be directed (a prerequisite: course A before course B) or undirected (a road between two cities), and weighted (travel time) or unweighted. Trees and grids are special graphs, and many interview questions hide a graph behind a story: words that differ by one letter, cells in a matrix, people who know each other, or network nodes sending signals.

Signals in a problem statement

Representations

Most problems give an edge list. Convert it to an adjacency list first:

from collections import defaultdict

def build(n, edges, directed=False):
    g = defaultdict(list)
    for u, v in edges:
        g[u].append(v)
        if not directed:
            g[v].append(u)
    return g

For grids, do not build anything: the neighbours of (r, c) are the four cells (r±1, c) and (r, c±1) that lie inside the grid.

Mental model

Ask three questions before coding: what is a node, what is an edge, and what am I searching for (reachability, shortest steps, an ordering, minimum cost)? The answer picks the algorithm.

Core patterns with templates

1. DFS for reachability and flood fill

def flood_fill(grid, r, c, new):
    old = grid[r][c]
    if old == new:
        return grid
    rows, cols = len(grid), len(grid[0])
    stack = [(r, c)]
    while stack:
        i, j = stack.pop()
        if 0 <= i < rows and 0 <= j < cols and grid[i][j] == old:
            grid[i][j] = new
            stack += [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]
    return grid

2. BFS for fewest steps (multi-source)

from collections import deque

def minutes_to_rot(grid):
    rows, cols = len(grid), len(grid[0])
    q = deque((i, j) for i in range(rows) for j in range(cols) if grid[i][j] == 2)
    fresh = sum(row.count(1) for row in grid)
    minutes = 0
    while q and fresh:
        for _ in range(len(q)):
            i, j = q.popleft()
            for a, b in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                if 0 <= a < rows and 0 <= b < cols and grid[a][b] == 1:
                    grid[a][b] = 2
                    fresh -= 1
                    q.append((a, b))
        minutes += 1
    return -1 if fresh else minutes

3. Topological sort (Kahn's algorithm)

def can_finish(n, prereqs):
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for a, b in prereqs:
        g[b].append(a)
        indeg[a] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    done = 0
    while q:
        u = q.popleft()
        done += 1
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return done == n

If some nodes never reach in-degree 0, there is a cycle.

4. Dijkstra for weighted shortest paths

import heapq

def dijkstra(n, edges, src):
    g = [[] for _ in range(n + 1)]
    for u, v, w in edges:
        g[u].append((v, w))
    dist = {src: 0}
    h = [(0, src)]
    while h:
        d, u = heapq.heappop(h)
        if d > dist.get(u, float("inf")):
            continue
        for v, w in g[u]:
            if d + w < dist.get(v, float("inf")):
                dist[v] = d + w
                heapq.heappush(h, (d + w, v))
    return dist

Complexity, mistakes and edge cases

Complexity

AlgorithmTimeSpace
DFS / BFSO(V + E)O(V)
Grid BFS / DFSO(rows × cols)O(rows × cols)
Topological sortO(V + E)O(V)
Dijkstra with a heapO((V + E) log V)O(V + E)
Union-find (with path compression and union by size)almost O(1) per operationO(V)

Common mistakes

Edge cases

Empty grid, a single cell, disconnected components, unreachable targets (return -1 or infinity as the problem says), self-loops, duplicate edges, the source equal to the target, and nodes numbered from 1 instead of 0.

Word-ladder style implicit graphs

When the graph is not given, generate neighbours on the fly. For words, try changing each position to each of 26 letters and keep only words in the dictionary set. That is O(L × 26) neighbours per word, much cheaper than comparing every pair of words.

Variations and practise

How interviewers twist it

def find(parent, x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

How to explain it

Start with the modelling: "Each cell is a node, edges join adjacent cells, and I need the fewest steps, so BFS." Interviewers grade the modelling step as heavily as the code.

Practise

The problems below cover reachability, flood fill, multi-source BFS on a grid, topological sort, Dijkstra, and an implicit word graph. For each, write down what a node and an edge are before choosing the algorithm.

Practise

Easy

Medium

Hard

Practise this in the app All guides