Graph Algorithms for Coding Interviews: BFS, DFS & Topo Sort

Graph problems — including grids, which are implicit graphs — are among the most-asked interview topics, and most reduce to two traversals: BFS (breadth-first, level by level) and DFS (depth-first). Add topological sort for dependency/ordering problems and you cover the large majority of graph questions.

When to recognize this pattern

The input is a grid, matrix, or explicit nodes-and-edges — or a problem about connectivity, paths, or ordering.
You need the shortest path in an unweighted graph → BFS. You need to explore/flood-fill or detect cycles → DFS.
There are prerequisites/dependencies → topological sort.

The template

BFS uses a queue and visits level by level (shortest path in unweighted graphs); DFS uses recursion or a stack:

from collections import deque
def bfs(start, neighbors):
    seen = {start}
    q = deque([(start, 0)])      # (node, distance)
    while q:
        node, dist = q.popleft()
        for nxt in neighbors(node):
            if nxt not in seen:
                seen.add(nxt)
                q.append((nxt, dist + 1))

def dfs(node, neighbors, seen):
    seen.add(node)
    for nxt in neighbors(node):
        if nxt not in seen:
            dfs(nxt, neighbors, seen)

Worked examples

Number of islands (flood fill)

Problem: Count islands of connected '1' cells in a grid.

DFS (or BFS) from each unvisited land cell, sinking the whole island; count how many times you start.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    def sink(r, c):
        if 0 <= r < rows and 0 <= c < cols and grid[r][c] == '1':
            grid[r][c] = '0'
            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
                sink(r, c)
    return count

O(rows×cols). Flood fill is the canonical grid-DFS — mark visited by mutating the grid (or a separate set if it's read-only).

Course schedule (topological sort)

Problem: Given courses and prerequisite pairs, can you finish all courses?

Cycle detection via Kahn's algorithm: peel off nodes with no remaining prerequisites; if you peel them all, no cycle.

from collections import deque, defaultdict
def canFinish(n, prereqs):
    graph = defaultdict(list)
    indeg = [0] * n
    for course, pre in prereqs:
        graph[pre].append(course)
        indeg[course] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    seen = 0
    while q:
        node = q.popleft(); seen += 1
        for nxt in graph[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0: q.append(nxt)
    return seen == n

O(V+E). Topological sort is the go-to for any dependency or ordering problem — build, compile, and course-ordering questions all reduce to it.

Rotting oranges (multi-source BFS)

Problem: Each minute, rotten oranges rot adjacent fresh ones. Return minutes until none are fresh, or -1.

BFS from all rotten cells at once (multi-source), counting levels as minutes.

from collections import deque
def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2: q.append((r, c, 0))
            elif grid[r][c] == 1: fresh += 1
    minutes = 0
    while q:
        r, c, t = q.popleft()
        minutes = max(minutes, t)
        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 and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                q.append((nr, nc, t + 1))
    return minutes if fresh == 0 else -1

O(rows×cols). Multi-source BFS — seeding the queue with every rotten cell — gives the simultaneous-spread behavior in one pass.

Variations & pitfalls

BFS for shortest path in unweighted graphs; DFS for exploration, cycle detection, and connected components.
Union-Find is the alternative for connectivity problems (number of components, valid tree) — near-constant per operation.
Pitfall: recursion-depth limits on large grids with DFS — switch to an explicit stack or BFS.

Pick BFS vs DFS instantly with live AI support

CoPilot Interview surfaces the optimal pattern and a working solution with Big-O in about 4 seconds during real Zoom and Teams calls. Free for Windows and macOS, invisible on screen-share.

Download free

FAQ

When should I use BFS vs DFS?

Use BFS (a queue, level by level) when you need the shortest path in an unweighted graph or simultaneous spread. Use DFS (recursion or a stack) for exploration, flood fill, cycle detection, and connected components. Both are O(V+E); the choice is about what the problem asks.

What is topological sort and when is it used?

Topological sort orders nodes so every dependency comes before what depends on it. Use it for any prerequisite/ordering problem - course schedule, build systems, task scheduling. Kahn's algorithm (peeling nodes with zero in-degree) also detects cycles.

How do I treat a grid as a graph?

Each cell is a node, and its up/down/left/right neighbors are edges. Most grid problems - number of islands, rotting oranges, shortest path in a maze - are just BFS or DFS on this implicit graph.

What is multi-source BFS?

BFS seeded with multiple starting nodes in the queue at once, so they expand simultaneously level by level. It's the clean solution for problems like rotting oranges or '0/1 matrix' where spread starts from many points at the same time.

When should I use Union-Find instead of BFS/DFS?

For pure connectivity questions - counting connected components, detecting whether adding edges forms a cycle, or checking if a graph is a valid tree. Union-Find with path compression handles these in near-constant time per operation.

Graph Algorithms for Coding Interviews