Algorithms & Coding Interviews · Graphs

Graph BFS, DFS & Grids

BFS and DFS solve most graph problems in O(V + E). Learn graph representations, when to choose BFS (shortest unweighted paths, multi-source spreading) or DFS (components, flood fill), how to treat grids as graphs, and watch BFS distances, Number of Islands and Rotting Oranges animated.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 14 min read▶ 3 interactive🛠️ 4 exercises

🎯 What you'll learn

Adjacency lists, matrices, edge lists and implicit grids
BFS for shortest unweighted paths; DFS for components
Multi-source BFS and reverse searches
Six LeetCode problems up to Word Ladder

📚 Before you start

Part 1The Pattern

A graph is a set of nodes connected by edges: cities and roads, users and friendships, services and calls, cells in a grid. Two traversals solve most graph interview problems: BFS explores level by level and finds shortest paths in unweighted graphs; DFS goes deep first and is the natural tool for connected components, flood fill, cycle detection and exhaustive search. Both visit each node and edge once: O(V + E).

BFS explores in rings of increasing distance from the source

1Representing a Graph

Representation	Space	Neighbour iteration	Use when
Adjacency list `adj[u] = [v, …]`	O(V + E)	O(deg u)	almost always (sparse graphs)
Adjacency matrix `m[u][v]`	O(V²)	O(V)	dense graphs, O(1) edge checks
Edge list `[(u, v, w)]`	O(E)	n/a	Kruskal, Bellman-Ford, input format
Implicit grid	none	4 (or 8) neighbours	islands, mazes, flood fill

Interview inputs usually arrive as an edge list or a grid; converting to an adjacency list is your first line of code. Ask whether edges are directed and whether the graph may be disconnected (then loop over all nodes as start points).

2Templates

typescript

function buildGraph(n: number, edges: number[][]): number[][] {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
  return adj;
}

function bfsDist(adj: number[][], src: number): number[] {
  const dist = new Array(adj.length).fill(-1);
  dist[src] = 0;
  const q = [src];
  for (let head = 0; head < q.length; head++) {        // head index: O(1) dequeue
    const u = q[head];
    for (const v of adj[u]) if (dist[v] === -1) { dist[v] = dist[u] + 1; q.push(v); }
  }
  return dist;
}

function countComponents(adj: number[][]): number {
  const seen = new Set<number>();
  let comps = 0;
  for (let s = 0; s < adj.length; s++) {
    if (seen.has(s)) continue;
    comps++;
    const stack = [s]; seen.add(s);
    while (stack.length) {
      const u = stack.pop()!;
      for (const v of adj[u]) if (!seen.has(v)) { seen.add(v); stack.push(v); }
    }
  }
  return comps;
}

function graphDemo(n: number, edges: number[][]): any[] {
  const adj = buildGraph(n, edges);
  return [bfsDist(adj, 0), countComponents(adj)];
}

python

from collections import deque

def build_graph(n, edges):                  # undirected adjacency list
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    return adj

def bfs_dist(adj, src):                     # shortest #edges from src (unweighted)
    dist = [-1] * len(adj)
    dist[src] = 0
    q = deque([src])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:               # mark when ENQUEUED, not when popped
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

def count_components(adj):                  # DFS with an explicit stack
    seen, comps = set(), 0
    for s in range(len(adj)):
        if s in seen:
            continue
        comps += 1
        stack = [s]; seen.add(s)
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if v not in seen:
                    seen.add(v); stack.append(v)
    return comps

def graph_demo(n, edges):
    adj = build_graph(n, edges)
    return [bfs_dist(adj, 0), count_components(adj)]

3BFS or DFS?

Question	Use
fewest steps / edges, nearest exit, minimum moves	BFS (first time you reach a node is the shortest)
spreading from many sources at once (rotting oranges, distance to nearest 0)	multi-source BFS: enqueue all sources first
count/label regions, flood fill, does a path exist	DFS or BFS (DFS is shorter to write)
detect a cycle, topological order, explore all paths	DFS
weighted shortest path	neither alone: Dijkstra (`04-shortest_paths`)

4Grids as Graphs

Each cell (r, c) is a node with up to four neighbours. Use a direction list and a bounds check; mark visited cells either in a seen set or by overwriting the grid (e.g. turning land "1" into water "0"), which saves memory but mutates the input (say so).

python

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
for dr, dc in DIRS:
    nr, nc = r + dr, c + dc
    if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == "1":
        ...

Under the HoodWhy BFS Finds Shortest Paths▾

BFS processes nodes in non-decreasing distance order: the queue always contains nodes at distance d followed by nodes at distance d + 1, never more than two layers. So the first time a node is discovered, it's via a shortest path. That's also why you mark nodes as visited when enqueuing: marking at pop time lets the same node enter the queue many times (still correct, but O(E) queue entries and slower). DFS has no such ordering, so a DFS path to a node is generally not the shortest.

⚠️ Common Pitfalls

Forgetting disconnected components: start a traversal from every unvisited node.
Marking visited too late in BFS (duplicate queue entries) or not at all (infinite loops on cycles).
Recursion depth in DFS on large grids (10⁶ cells): use an explicit stack in Python.
queue.shift() in JS: O(n) per dequeue; use a head index.
Mutating input grids without saying so.

📋 Quick Reference

text

adj = [[] for _ in range(n)]; for a,b in edges: adj[a].append(b); adj[b].append(a)
BFS: q=[src]; dist[src]=0; pop u; for v in adj[u]: if unseen: mark, dist, push
DFS: stack/recursion; mark on push; count components by starting from each unseen node
grid: 4 directions + bounds check · multi-source BFS: push all sources first
O(V + E) time · O(V) space

Part 2Interview Problems

Six problems: flood fills and region counting on grids, multi-source BFS, deep-copying graphs, reverse searches from the borders, and BFS over an implicit word graph.

1Number of Islands (LeetCode 200)

🟠 Medium. Count islands in a grid of "1" (land) and "0" (water); land connects horizontally and vertically.

text

4×5 grid with three separate land groups → 3

Approach. Scan every cell; when you find unvisited land, it's a new island: increment the count and flood-fill (DFS/BFS) all connected land, marking it visited (here by sinking it to "0").

Complexity. O(R · C) time, O(R · C) worst-case stack/queue.

typescript

function numIslands(grid: string[][]): number {
  const R = grid.length, C = grid[0].length;
  let count = 0;
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r][c] !== "1") continue;
      count++;
      const stack: [number, number][] = [[r, c]];
      grid[r][c] = "0";
      while (stack.length) {
        const [i, j] = stack.pop()!;
        for (const [di, dj] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
          const ni = i + di, nj = j + dj;
          if (ni >= 0 && nj >= 0 && ni < R && nj < C && grid[ni][nj] === "1") {
            grid[ni][nj] = "0";
            stack.push([ni, nj]);
          }
        }
      }
    }
  }
  return count;
}

python

def num_islands(grid):
    R, C = len(grid), len(grid[0])
    count = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] != "1":
                continue
            count += 1
            stack = [(r, c)]
            grid[r][c] = "0"                       # sink as we go
            while stack:
                i, j = stack.pop()
                for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    ni, nj = i + di, j + dj
                    if 0 <= ni < R and 0 <= nj < C and grid[ni][nj] == "1":
                        grid[ni][nj] = "0"
                        stack.append((ni, nj))
    return count

2Flood Fill (LeetCode 733)

🟢 Easy. Starting at (sr, sc), repaint the connected region of the starting colour with color.

text

[[1,1,1],[1,1,0],[1,0,1]], start (1,1), color 2 → [[2,2,2],[2,2,0],[2,0,1]]

Approach. DFS from the start, recolouring cells that still have the original colour. If the new colour equals the original, return immediately (otherwise the DFS would never terminate).

Complexity. O(R · C) time.

typescript

function floodFill(image: number[][], sr: number, sc: number, color: number): number[][] {
  const orig = image[sr][sc];
  if (orig === color) return image;
  const R = image.length, C = image[0].length;
  const stack: [number, number][] = [[sr, sc]];
  while (stack.length) {
    const [r, c] = stack.pop()!;
    if (r < 0 || c < 0 || r >= R || c >= C || image[r][c] !== orig) continue;
    image[r][c] = color;
    stack.push([r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]);
  }
  return image;
}

python

def flood_fill(image, sr, sc, color):
    orig = image[sr][sc]
    if orig == color:
        return image
    R, C = len(image), len(image[0])
    stack = [(sr, sc)]
    while stack:
        r, c = stack.pop()
        if 0 <= r < R and 0 <= c < C and image[r][c] == orig:
            image[r][c] = color
            stack.extend(((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)))
    return image

3Rotting Oranges (LeetCode 994)

🟠 Medium. Each minute, rotten oranges (2) rot their fresh (1) neighbours. Return the minutes until no fresh orange remains, or −1 if impossible.

text

[[2,1,1],[1,1,0],[0,1,1]] → 4

Approach. Multi-source BFS: enqueue every rotten orange at time 0 and count fresh ones. Process the queue level by level; each level is one minute. At the end, any remaining fresh orange means −1.

Complexity. O(R · C) time and space.

typescript

function orangesRotting(grid: number[][]): number {
  const R = grid.length, C = grid[0].length;
  let level: [number, number][] = [], fresh = 0;
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) {
    if (grid[r][c] === 2) level.push([r, c]);
    else if (grid[r][c] === 1) fresh++;
  }
  let minutes = 0;
  while (level.length && fresh) {
    const next: [number, number][] = [];
    for (const [r, c] of level) {
      for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nc >= 0 && nr < R && nc < C && grid[nr][nc] === 1) {
          grid[nr][nc] = 2; fresh--; next.push([nr, nc]);
        }
      }
    }
    level = next;
    minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

python

from collections import deque

def oranges_rotting(grid):
    R, C = len(grid), len(grid[0])
    q, fresh = deque(), 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 2:
                q.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while q and fresh:
        for _ in range(len(q)):                 # one minute = one BFS level
            r, c = q.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1

4Clone Graph (LeetCode 133)

🟠 Medium. Return a deep copy of a connected undirected graph given a reference to one node (each node has a value and a list of neighbours).

text

adjacency [[2,4],[1,3],[2,4],[1,3]] → an identical, separate graph

Approach. DFS/BFS with a map from original node to its clone. When visiting a node, create its clone if missing, then connect the clone to the clones of all neighbours. The map doubles as the visited set and handles cycles.

Complexity. O(V + E) time and space.

typescript

class GNode {
  val: number;
  neighbors: GNode[];
  constructor(val = 0, neighbors: GNode[] = []) { this.val = val; this.neighbors = neighbors; }
}

function cloneGraph(node: GNode | null): GNode | null {
  if (!node) return null;
  const clones = new Map<GNode, GNode>([[node, new GNode(node.val)]]);
  const stack = [node];
  while (stack.length) {
    const cur = stack.pop()!;
    for (const nb of cur.neighbors) {
      if (!clones.has(nb)) { clones.set(nb, new GNode(nb.val)); stack.push(nb); }
      clones.get(cur)!.neighbors.push(clones.get(nb)!);
    }
  }
  return clones.get(node)!;
}

python

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors or []

def clone_graph(node):
    if not node:
        return None
    clones = {node: Node(node.val)}
    stack = [node]
    while stack:
        cur = stack.pop()
        for nb in cur.neighbors:
            if nb not in clones:
                clones[nb] = Node(nb.val)
                stack.append(nb)
            clones[cur].neighbors.append(clones[nb])
    return clones[node]

5Pacific Atlantic Water Flow (LeetCode 417)

🟠 Medium. Water flows from a cell to neighbours of equal or lower height. Return cells from which water can reach both the Pacific (top/left edges) and the Atlantic (bottom/right edges).

text

5×5 heights → [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Approach. Reverse the flow: run a DFS/BFS from each ocean's border cells uphill (to neighbours with height ≥ current). Cells reached by both searches are the answer. Two traversals instead of one search per cell.

Complexity. O(R · C) time and space.

typescript

function pacificAtlantic(heights: number[][]): number[][] {
  const R = heights.length, C = heights[0].length;
  const reach = (starts: [number, number][]): boolean[][] => {
    const seen = Array.from({ length: R }, () => new Array(C).fill(false));
    const stack = [...starts];
    for (const [r, c] of starts) seen[r][c] = true;
    while (stack.length) {
      const [r, c] = stack.pop()!;
      for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nc >= 0 && nr < R && nc < C && !seen[nr][nc] && heights[nr][nc] >= heights[r][c]) {
          seen[nr][nc] = true; stack.push([nr, nc]);
        }
      }
    }
    return seen;
  };
  const border = (top: boolean): [number, number][] => {
    const s: [number, number][] = [];
    for (let c = 0; c < C; c++) s.push([top ? 0 : R - 1, c]);
    for (let r = 0; r < R; r++) s.push([r, top ? 0 : C - 1]);
    return s;
  };
  const pac = reach(border(true)), atl = reach(border(false));
  const res: number[][] = [];
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (pac[r][c] && atl[r][c]) res.push([r, c]);
  return res;
}

python

def pacific_atlantic(heights):
    R, C = len(heights), len(heights[0])

    def reach(starts):
        seen = set(starts)
        stack = list(starts)
        while stack:
            r, c = stack.pop()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in seen and heights[nr][nc] >= heights[r][c]:
                    seen.add((nr, nc))
                    stack.append((nr, nc))
        return seen

    pac = reach([(0, c) for c in range(C)] + [(r, 0) for r in range(R)])
    atl = reach([(R - 1, c) for c in range(C)] + [(r, C - 1) for r in range(R)])
    return [[r, c] for r, c in pac & atl]

6Word Ladder (LeetCode 127)

🔴 Hard. Return the number of words in the shortest transformation sequence from beginWord to endWord, changing one letter at a time, where every intermediate word is in wordList (0 if impossible).

text

"hit" → "cog" with [hot,dot,dog,lot,log,cog] → 5   (hit → hot → dot → dog → cog)

Approach. BFS over words: neighbours differ by one letter. Generate neighbours by trying all 26 letters at each position and keeping those in the word set (remove them when enqueued, as the visited mark). The BFS level when endWord is reached is the answer.

Complexity. O(N · L · 26) time for N words of length L.

typescript

function ladderLength(begin: string, end: string, wordList: string[]): number {
  const words = new Set(wordList);
  if (!words.has(end)) return 0;
  let level = [begin], steps = 1;
  while (level.length) {
    const next: string[] = [];
    for (const word of level) {
      if (word === end) return steps;
      for (let i = 0; i < word.length; i++) {
        for (let k = 0; k < 26; k++) {
          const nxt = word.slice(0, i) + String.fromCharCode(97 + k) + word.slice(i + 1);
          if (words.has(nxt)) { words.delete(nxt); next.push(nxt); }
        }
      }
    }
    level = next;
    steps++;
  }
  return 0;
}

python

from collections import deque

def ladder_length(begin, end, word_list):
    words = set(word_list)
    if end not in words:
        return 0
    q = deque([(begin, 1)])
    while q:
        word, steps = q.popleft()
        if word == end:
            return steps
        for i in range(len(word)):
            for ch in "abcdefghijklmnopqrstuvwxyz":
                nxt = word[:i] + ch + word[i + 1:]
                if nxt in words:
                    words.remove(nxt)              # visited
                    q.append((nxt, steps + 1))
    return 0

🧠 Key takeaways

Convert inputs to an adjacency list; grids are graphs with 4 implicit neighbours.
BFS = shortest path in unweighted graphs (mark visited when enqueuing).
DFS = components, flood fill, cycles; use an explicit stack for big inputs.
Multi-source BFS spreads from all sources at once; reverse searches start from the goal.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_graph_bfs_dfs_and_grids_exercise_1.py

TS PY

algo_graph_bfs_dfs_and_grids_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. Fewest moves in an unweighted maze: BFS or DFS?

BFS reaches nodes in distance order.

2. Rotting Oranges starts the BFS with…

Multi-source BFS.

3. When should BFS mark a node visited?

Prevents duplicate queue entries.

4. Time complexity of BFS/DFS with an adjacency list?

Each node and edge once.

Source: algo_graph_bfs_dfs_and_grids_theory_1.md, algo_graph_bfs_dfs_and_grids_theory_2.md · generated by tools/build_lessons.py