Graphs: BFS, DFS, Topological Sort, Union-Find

Graphs look intimidating, but interview graph problems reduce to four tools on top of one structure (an adjacency list). Learn when to use each and most graph questions become routine — including grid problems, which are graphs in disguise.

The idea

Represent the graph as an adjacency list ({node: [neighbours]}). Then choose:

• BFS (queue) — shortest path in an unweighted graph, level structure.
• DFS (recursion/stack) — reachability, connected components, islands, cycle detection.
• Topological sort — ordering tasks with dependencies (and detecting cycles).
• Union-Find (disjoint set) — ”are these connected?”, counting components, detecting cycles as edges are added.

A huge class of problems are grids — treat each cell as a node connected to its up-to-4 neighbours.

DFS: number of islands (grid as graph)

Flood-fill each unvisited land cell, marking it visited; count how many flood-fills you start:

def num_islands(grid):
    if not grid: return 0
    R, C = len(grid), len(grid[0]); count = 0
    def dfs(r, c):
        if r < 0 or c < 0 or r >= R or c >= C or grid[r][c] != '1':
            return
        grid[r][c] = '0'                       # mark visited
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
    for r in range(R):
        for c in range(C):
            if grid[r][c] == '1':
                count += 1; dfs(r, c)
    return count

Topological sort: course schedule

Can you finish all courses given prerequisites? Compute each node’s in-degree, start from the zero-in-degree nodes, and repeatedly remove them (Kahn’s algorithm). If you process all nodes, there’s no cycle:

from collections import defaultdict, deque
def can_finish(n, prereqs):
    adj = defaultdict(list); indeg = [0]*n
    for a, b in prereqs:            # b -> a (b is a prerequisite of a)
        adj[b].append(a); indeg[a] += 1
    q = deque([i for i in range(n) if indeg[i] == 0])
    seen = 0
    while q:
        u = q.popleft(); seen += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return seen == n               # all processed → no cycle
# can_finish(2, [[1,0]]) -> True ;  can_finish(2, [[1,0],[0,1]]) -> False

Union-Find: detect a redundant connection

Union-Find answers connectivity and detects the edge that creates a cycle, near O(1) per operation with path compression:

def find_redundant(edges):
    parent = list(range(len(edges) + 1))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]      # path compression
            x = parent[x]
        return x
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:                           # already connected → this edge makes a cycle
            return [a, b]
        parent[ra] = rb                        # union
    return []
# find_redundant([[1,2],[1,3],[2,3]]) -> [2,3]

Step-by-step walkthrough

Trace Course Schedule II (topological sort, Kahn’s algorithm) with 4 courses and prerequisites 0→1, 0→2, 1→3, 2→3. Start with every course that has no prerequisites; taking a course lowers its dependents’ in-degree, and any that hit zero become available.

Order: [0, 1, 2, 3]. All 4 courses were processed, so there is no cycle. If a cycle existed, some in-degree would never reach zero and the order would come up short — that’s the cycle check.

When to reach for which

• “Shortest path / fewest steps” (unweighted) → BFS (word ladder, shortest path in a grid).
• “Explore / count regions / detect a cycle” → DFS (islands, clone graph, flood fill).
• “Order tasks with dependencies” / “is it possible given prerequisites” → topological sort (course schedule, alien dictionary).
• “Are these connected? / number of groups / redundant edge” → union-find.
• “Shortest path with weights” → Dijkstra (a heap-based BFS, Lesson 14’s heap + graph).

Pitfalls

• Not marking visited. Infinite loops come from re-visiting nodes. Mark on enqueue/visit, not on dequeue, for BFS to avoid duplicates.
• DFS recursion depth on big grids. A huge grid can blow the stack; mention an explicit stack or BFS if asked.
• Topo sort on a cyclic graph. If not all nodes are processed, there’s a cycle — that is often the answer (can’t finish).

Recap

Build an adjacency list, then pick the tool: BFS for shortest unweighted paths, DFS for components/cycles/islands, topological sort (in-degrees, Kahn’s) for dependency ordering, union-find for connectivity. Grids are graphs (cells = nodes). For weighted shortest paths, Dijkstra (heap + BFS). Signal words: connected, shortest, schedule/order, islands, redundant edge.

Practice: 12 solved problems on graphs → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 17 — Dynamic Programming I (1-D).