Graphs

1What a graph is, and why it's everywhere

A graph is the most general "things and relationships" structure: nodes (vertices) connected by edges. Drop the tree's rules — no root, no parent/child, cycles allowed, disconnected pieces allowed — and you get a graph. (A tree is just a connected, acyclic graph. Linked lists too. You've been doing graphs all along.)

Three flavors change which algorithm you reach for:

2Representations

Interview problems hand you graphs in three costumes.

Adjacency list — the default

node → list of neighbors. Space O(V + E). This is what you build from an edge list in the first 30 seconds of almost every graph problem:

from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)     # drop this line for directed graphs

  0 ─── 1
   \   /
    \ /
     2 ─── 3

0: [1, 2]
1: [0, 2]
2: [0, 1, 3]
3: [2]

Adjacency matrix

matrix[u][v] = 1/weight. O(1) edge lookup, but O(V²) space — only for small dense graphs (or Floyd–Warshall).

Implicit graph — the sneaky one

Nobody gives you edges; the rules generate neighbors. A grid cell's neighbors are its 4 adjacent cells. A word's neighbors are words one letter away. A state's neighbors are states one move away.

3BFS and DFS — the only two ways to explore

Every graph traversal answers one question: what do I visit next? There are exactly two disciplined answers, and everything else is a variation.

• BFS: visit all nodes at distance 1, then distance 2, then 3… — expand like a ripple. Uses a queue (FIFO: first discovered, first expanded).
• DFS: follow one path as deep as it goes, backtrack, try the next — probe like a maze-runner with a ball of string. Uses a stack (explicit, or the call stack).

      A          layer 0
     / \
    B   C        layer 1
   / \   \
  D   E   F      layer 2
order: A B C D E F

      A
      │ go deep: A→B→D …
      │ dead end, backtrack
      │ to B, try E …
      ▼
order: A B D E C F

BFS — with the layer structure explicit

from collections import deque

def bfs(graph, start):
    dist = {start: 0}
    q = deque([start])
    while q:
        node = q.popleft()
        for nb in graph[node]:
            if nb not in dist:          # dist doubles as visited
                dist[nb] = dist[node] + 1
                q.append(nb)
    return dist

DFS — recursive and iterative

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for nb in graph[start]:
        if nb not in visited:
            dfs(graph, nb, visited)
    return visited

def dfs_iter(graph, start):
    visited, stack = set(), [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        stack.extend(nb for nb in graph[node]
                     if nb not in visited)
    return visited

DFS's superpowers: exhaustively exploring components, detecting cycles, topological ordering, and anything path-shaped/backtracking-shaped. It's usually less code, which matters under time pressure.

4Connected components & grid problems (Number of Islands)

Component counting = "how many separate blobs": loop over all nodes; every time you find an unvisited one, that's a new component — flood it (BFS or DFS) to mark the whole blob.

Number of Islands is exactly this with an implicit grid graph — cells are nodes, edges connect adjacent land. Here's a grid with its three islands flood-filled in three colors:

Three colors = three flood fills = 3 islands. Diagonals don't connect (only 4-adjacency), so the green and amber blobs stay separate.

def num_islands(grid):
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def sink(r, c):                              # DFS flood fill
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
            return
        grid[r][c] = "0"                         # mark visited by sinking
        sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1                       # new island discovered
                sink(r, c)                       # erase it entirely
    return count

O(rows × cols): each cell visited O(1) times. The grid toolkit generalizes to Max Area of Island, Flood Fill, Surrounded Regions, Pacific-Atlantic (flood from the borders — a lovely inversion), and Rotting Oranges (multi-source BFS: seed the queue with all rotten oranges at t=0; layers = minutes).

Grid idiom worth pre-memorizing:

for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        ...

5Topological sort — ordering a DAG

The question it answers: given dependencies ("A before B"), produce a valid execution order — or report that none exists (a cycle). This is docker-compose startup order, DB migration ordering, build systems, Airflow scheduling. Interview costume: Course Schedule.

Kahn's algorithm (BFS flavor) — the one to know cold. Intuition: something with no prerequisites can go first. Do it, delete it, repeat. Track each node's in-degree (how many prerequisites still point at it); anything at 0 is ready.

from collections import deque, defaultdict

def topo_sort(num_nodes, edges):          # edges: (u, v) = u before v
    graph = defaultdict(list)
    indegree = [0] * num_nodes
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    q = deque(n for n in range(num_nodes) if indegree[n] == 0)
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nb in graph[node]:
            indegree[nb] -= 1             # "delete" the edge
            if indegree[nb] == 0:         # all prereqs satisfied → ready
                q.append(nb)

    return order if len(order) == num_nodes else []   # short order ⇒ cycle!

DFS flavor: postorder DFS, then reverse — a node finishes only after everything it points to has finished. Know it exists; write Kahn's.

Cycle detection, summarized

Directed graph: Kahn's leftover-nodes check, or DFS with three colors:

• white — unvisited, never touched
• gray — in the current recursion stack, i.e. on the path you're standing on right now
• black — fully done, all descendants explored

Hitting a gray node = back edge = cycle. Gray is the crucial subtlety — hitting a black node is fine (just a shared dependency, like two services importing the same library).

Undirected graph: DFS; seeing a visited neighbor that isn't your immediate parent = cycle. Or union-find (§7): an edge joining two nodes already in the same set closes a cycle.

6Shortest paths with weights — Dijkstra

BFS's "first visit = shortest" breaks with weights: a 2-hop path of weight 1+1 beats a 1-hop path of weight 10, but BFS finds the 1-hop first.

Dijkstra's fix — greedy by total distance: always expand the frontier node with the smallest known total distance from the source. That's BFS where the queue becomes a min-heap keyed by distance.

import heapq

def dijkstra(graph, src):                 # graph[u] = [(v, weight), ...]
    dist = {src: 0}
    pq = [(0, src)]                       # (distance-so-far, node)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')):
            continue                      # stale entry — already found better
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))   # "lazy deletion": push, skip stale later
    return dist

The if d > dist[u]: continue line is the idiomatic Python move — instead of decreasing a key inside the heap (which heapq can't do), push duplicates and skip outdated ones on pop. O((V + E) log V). Costume versions: Network Delay Time, Cheapest Flights (K stops — a twist), Path With Minimum Effort.

7Union-Find (Disjoint Set Union)

The question it answers: "are these two things in the same group?" under a stream of merges — without re-running traversals. Dynamic connectivity: accounts that share an email, network nodes as cables get added, Kruskal's MST, friend circles.

Each group is a tree; each node points at a parent; the root is the group's ID. find walks to the root; union links two roots.

find(D): D → B → A (root)
        A
       / \
      B   C
      │
      D

union(A-tree, C-tree):
point C's root at A
         A
        /|\
       B C E
       │
       D

Two optimizations make it effectively O(1) per op (inverse-Ackermann, α(n) ≤ 4 for any physical n):

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path compression (halving)
            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 connected (⇒ this edge makes a cycle)
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                # union by rank: shallow under deep
        self.rank[ra] += self.rank[ra] == self.rank[rb]
        return True

• Path compression: while finding the root, make nodes point closer to it — trees flatten themselves through use.
• Union by rank: attach the shorter tree under the taller — trees stay shallow.

When to prefer it over DFS: edges arrive over time / queries interleave with merges ("after adding each cable, are X and Y connected?"). For a static graph given up front, plain DFS components are simpler. union returning False doubles as undirected cycle detection (Redundant Connection).

8When interview problems are secretly graphs

The pattern-recognition section. If the problem contains states and legal moves between them, it's a graph search:

9Common interview questions

10Self-test

Answer from memory, then open each spot-check.