Graphs: BFS & DFS

Graph terminology

A graph is a set of vertices (nodes) connected by edges.

• Directed — edges have direction (A → B does not imply B → A). Examples: Twitter follows, dependency graphs.
• Undirected — edges are bidirectional. Examples: Facebook friends, road networks.
• Weighted — edges carry a cost/distance. Unweighted — all edges are equal.
• Degree — number of edges connected to a vertex. In directed graphs: in-degree (edges coming in) and out-degree (edges going out).
• Adjacency — two vertices are adjacent if connected by an edge.
• Connected component — a maximal set of vertices where every pair is reachable from every other.
• Cycle — a path that starts and ends at the same vertex.

Graph representations

Adjacency list — O(V + E) space, best for sparse graphs

// Undirected graph with V vertices
const graph = new Map<number, number[]>()

function addEdge(u: number, v: number): void {
  if (!graph.has(u)) graph.set(u, [])
  if (!graph.has(v)) graph.set(v, [])
  graph.get(u)!.push(v)
  graph.get(v)!.push(u)  // omit for directed graphs
}

Use an adjacency list almost always. It iterates only actual neighbors, so traversal is O(V + E).

Adjacency matrix — O(V²) space, best for dense graphs or O(1) edge lookup

const V = 5
const matrix: number[][] = Array.from({ length: V }, () => new Array(V).fill(0))

function addEdge(u: number, v: number, weight = 1): void {
  matrix[u][v] = weight
  matrix[v][u] = weight  // omit for directed
}

// O(1) edge check
function hasEdge(u: number, v: number): boolean {
  return matrix[u][v] !== 0
}

Edge list — simplest representation

type Edge = [number, number]        // unweighted
type WeightedEdge = [number, number, number]  // [from, to, weight]

const edges: Edge[] = [[0,1],[1,2],[2,3]]

Edge lists are used in algorithms like Kruskal’s MST that sort edges by weight.

BFS — Breadth-First Search

BFS explores layer by layer. It visits all nodes at distance 1 before distance 2, making it ideal for shortest path in unweighted graphs.

function bfs(graph: Map<number, number[]>, start: number): number[] {
  const visited = new Set<number>()
  const queue: number[] = [start]
  const order: number[] = []

  visited.add(start)               // mark BEFORE enqueue to avoid double-visits

  while (queue.length > 0) {
    const node = queue.shift()!
    order.push(node)

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor)      // mark here, not when popped
        queue.push(neighbor)
      }
    }
  }
  return order
}

Time: O(V + E) — every vertex and edge is processed once.
Space: O(V) — the visited set and queue.

Critical bug to avoid: Mark visited when you enqueue, not when you dequeue. If you mark on dequeue, the same node can be enqueued multiple times from different neighbors before it’s popped, causing redundant work or wrong shortest-path counts.

BFS pattern: shortest path (unweighted)

function shortestPath(
  graph: Map<number, number[]>,
  start: number,
  end: number
): number {
  if (start === end) return 0
  const visited = new Set<number>([start])
  const queue: [number, number][] = [[start, 0]]  // [node, distance]

  while (queue.length > 0) {
    const [node, dist] = queue.shift()!
    for (const neighbor of graph.get(node) ?? []) {
      if (neighbor === end) return dist + 1
      if (!visited.has(neighbor)) {
        visited.add(neighbor)
        queue.push([neighbor, dist + 1])
      }
    }
  }
  return -1  // unreachable
}

BFS pattern: multi-source BFS

Start BFS from multiple sources simultaneously. All sources are enqueued at distance 0 before the loop begins.

Rotting Oranges (LC 994) — every rotten orange spreads to fresh neighbors each minute:

function orangesRotting(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length
  const queue: [number, number][] = []
  let fresh = 0

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c])
      if (grid[r][c] === 1) fresh++
    }
  }

  if (fresh === 0) return 0
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]]
  let minutes = 0

  while (queue.length > 0 && fresh > 0) {
    const size = queue.length
    minutes++
    for (let i = 0; i < size; i++) {
      const [r, c] = queue.shift()!
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
          grid[nr][nc] = 2
          fresh--
          queue.push([nr, nc])
        }
      }
    }
  }
  return fresh === 0 ? minutes : -1
}

BFS pattern: Word Ladder (LC 127)

Transform one word to another changing one letter at a time. BFS guarantees the minimum number of transformations.

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const wordSet = new Set(wordList)
  if (!wordSet.has(endWord)) return 0

  const queue: [string, number][] = [[beginWord, 1]]
  const visited = new Set<string>([beginWord])

  while (queue.length > 0) {
    const [word, steps] = queue.shift()!
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) {          // 'a' to 'z'
        const next = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1)
        if (next === endWord) return steps + 1
        if (wordSet.has(next) && !visited.has(next)) {
          visited.add(next)
          queue.push([next, steps + 1])
        }
      }
    }
  }
  return 0
}

Bidirectional BFS optimization: Run BFS from both beginWord and endWord simultaneously, expanding the smaller frontier each step. This reduces the search space from O(b^d) to O(b^(d/2)) where b is branching factor and d is depth.

DFS — Depth-First Search

DFS goes as deep as possible along each branch before backtracking.

Recursive DFS

function dfsRecursive(
  graph: Map<number, number[]>,
  node: number,
  visited: Set<number>
): void {
  visited.add(node)
  for (const neighbor of graph.get(node) ?? []) {
    if (!visited.has(neighbor)) {
      dfsRecursive(graph, neighbor, visited)
    }
  }
}

Iterative DFS (explicit stack)

function dfsIterative(graph: Map<number, number[]>, start: number): number[] {
  const visited = new Set<number>()
  const stack = [start]
  const order: number[] = []

  while (stack.length > 0) {
    const node = stack.pop()!
    if (visited.has(node)) continue
    visited.add(node)
    order.push(node)
    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) stack.push(neighbor)
    }
  }
  return order
}

Note: iterative DFS visits neighbors in reverse order compared to recursive DFS (due to stack LIFO). This rarely matters for correctness.

DFS pattern: connected components

function countComponents(n: number, edges: number[][]): number {
  const graph = new Map<number, number[]>()
  for (let i = 0; i < n; i++) graph.set(i, [])
  for (const [u, v] of edges) {
    graph.get(u)!.push(v)
    graph.get(v)!.push(u)
  }

  const visited = new Set<number>()
  let components = 0

  for (let i = 0; i < n; i++) {
    if (!visited.has(i)) {
      dfsRecursive(graph, i, visited)
      components++
    }
  }
  return components
}

DFS pattern: Number of Islands (LC 200)

Grids are implicit graphs — each cell is a vertex, edges connect adjacent cells. 4-directional: up/down/left/right. 8-directional adds diagonals.

function numIslands(grid: string[][]): number {
  const rows = grid.length, cols = grid[0].length
  let islands = 0

  function dfs(r: number, c: number): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return
    grid[r][c] = '0'                  // mark visited by mutating grid (restore if needed)
    dfs(r + 1, c); dfs(r - 1, c)
    dfs(r, c + 1); dfs(r, c - 1)
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') { dfs(r, c); islands++ }
    }
  }
  return islands
}

Max Area of Island (LC 695) — same pattern, return count from DFS instead:

function maxAreaOfIsland(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length

  function dfs(r: number, c: number): number {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== 1) return 0
    grid[r][c] = 0
    return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1)
  }

  let max = 0
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === 1) max = Math.max(max, dfs(r, c))
  return max
}

Cycle detection: directed graph (white/gray/black coloring)

Three states per node:

• White (0): unvisited
• Gray (1): currently in the DFS call stack (on the current path)
• Black (2): fully processed

A back edge (gray → gray) means a cycle.

function hasCycleDirected(numCourses: number, prerequisites: number[][]): boolean {
  const graph = new Map<number, number[]>()
  for (let i = 0; i < numCourses; i++) graph.set(i, [])
  for (const [a, b] of prerequisites) graph.get(b)!.push(a)

  const color = new Array(numCourses).fill(0)  // 0=white,1=gray,2=black

  function dfs(node: number): boolean {
    color[node] = 1                             // mark gray: on current path
    for (const neighbor of graph.get(node)!) {
      if (color[neighbor] === 1) return true    // back edge → cycle
      if (color[neighbor] === 0 && dfs(neighbor)) return true
    }
    color[node] = 2                             // mark black: fully explored
    return false
  }

  for (let i = 0; i < numCourses; i++)
    if (color[i] === 0 && dfs(i)) return true
  return false
}

Cycle detection: undirected graph (parent tracking)

In undirected graphs, every edge appears twice. Track the parent to avoid treating the edge you came from as a back edge.

function hasCycleUndirected(n: number, edges: number[][]): boolean {
  const graph = new Map<number, number[]>()
  for (let i = 0; i < n; i++) graph.set(i, [])
  for (const [u, v] of edges) {
    graph.get(u)!.push(v)
    graph.get(v)!.push(u)
  }

  const visited = new Set<number>()

  function dfs(node: number, parent: number): boolean {
    visited.add(node)
    for (const neighbor of graph.get(node)!) {
      if (neighbor === parent) continue         // the edge we came from
      if (visited.has(neighbor)) return true    // back edge → cycle
      if (dfs(neighbor, node)) return true
    }
    return false
  }

  for (let i = 0; i < n; i++)
    if (!visited.has(i) && dfs(i, -1)) return true
  return false
}

Bipartite graph check (LC 785)

A graph is bipartite if vertices can be colored with 2 colors such that no two adjacent vertices share a color. Equivalent to: the graph has no odd-length cycles.

function isBipartite(graph: number[][]): boolean {
  const color = new Array(graph.length).fill(-1)

  for (let start = 0; start < graph.length; start++) {
    if (color[start] !== -1) continue
    const queue: number[] = [start]
    color[start] = 0

    while (queue.length > 0) {
      const node = queue.shift()!
      for (const neighbor of graph[node]) {
        if (color[neighbor] === -1) {
          color[neighbor] = 1 - color[node]    // flip color
          queue.push(neighbor)
        } else if (color[neighbor] === color[node]) {
          return false                          // same color → not bipartite
        }
      }
    }
  }
  return true
}

Clone Graph (LC 133)

DFS with a hash map to track already-cloned nodes (handles cycles):

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

function cloneGraph(node: _Node | null): _Node | null {
  if (!node) return null
  const cloned = new Map<_Node, _Node>()

  function dfs(n: _Node): _Node {
    if (cloned.has(n)) return cloned.get(n)!
    const copy = new _Node(n.val)
    cloned.set(n, copy)
    for (const neighbor of n.neighbors)
      copy.neighbors.push(dfs(neighbor))
    return copy
  }

  return dfs(node)
}

Pacific Atlantic Water Flow (LC 417)

Instead of simulating water flow forward (expensive), reverse the problem: do BFS/DFS from the ocean borders inward, finding all cells that can reach each ocean. The answer is cells reachable by both.

function pacificAtlantic(heights: number[][]): number[][] {
  const rows = heights.length, cols = heights[0].length
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]]

  function bfs(starts: [number,number][]): boolean[][] {
    const reachable: boolean[][] = Array.from({length: rows}, () => new Array(cols).fill(false))
    const queue = [...starts]
    for (const [r,c] of starts) reachable[r][c] = true

    while (queue.length > 0) {
      const [r, c] = queue.shift()!
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
            && !reachable[nr][nc]
            && heights[nr][nc] >= heights[r][c]) {  // water flows downhill → reversed
          reachable[nr][nc] = true
          queue.push([nr, nc])
        }
      }
    }
    return reachable
  }

  const pacificStarts: [number,number][] = []
  const atlanticStarts: [number,number][] = []
  for (let r = 0; r < rows; r++) {
    pacificStarts.push([r, 0])
    atlanticStarts.push([r, cols - 1])
  }
  for (let c = 0; c < cols; c++) {
    pacificStarts.push([0, c])
    atlanticStarts.push([rows - 1, c])
  }

  const pac = bfs(pacificStarts)
  const atl = bfs(atlanticStarts)
  const result: number[][] = []

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (pac[r][c] && atl[r][c]) result.push([r, c])

  return result
}

Course Schedule (LC 207) — directed cycle detection

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  return !hasCycleDirected(numCourses, prerequisites)
}
// Uses hasCycleDirected from the cycle detection section above.
// If there's a cycle in the prerequisite graph, courses cannot all be finished.

Course Schedule II (LC 210) — topological sort order. If no cycle, return post-order DFS traversal reversed:

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const graph = new Map<number, number[]>()
  for (let i = 0; i < numCourses; i++) graph.set(i, [])
  for (const [a, b] of prerequisites) graph.get(b)!.push(a)

  const color = new Array(numCourses).fill(0)
  const order: number[] = []

  function dfs(node: number): boolean {
    color[node] = 1
    for (const neighbor of graph.get(node)!) {
      if (color[neighbor] === 1) return false   // cycle
      if (color[neighbor] === 0 && !dfs(neighbor)) return false
    }
    color[node] = 2
    order.push(node)                            // post-order
    return true
  }

  for (let i = 0; i < numCourses; i++)
    if (color[i] === 0 && !dfs(i)) return []

  return order.reverse()
}

Complexity reference

Common mistakes

1. Marking visited on dequeue (not enqueue) — the #1 BFS bug. Nodes get enqueued multiple times, breaking distance counts and causing TLE.
2. Forgetting disconnected components — always loop over all nodes when looking for global properties.
3. Using adjacency matrix for sparse graphs — O(V²) space and time to iterate all neighbors.
4. Off-by-one in grid bounds — always check r >= 0 && r < rows && c >= 0 && c < cols.
5. Not restoring state — if mutating the grid to mark visited, restore it if the grid is needed after traversal.
6. DFS cycle detection: using a plain visited set in directed graphs — a visited set only tells you if you’ve seen a node before, not if it’s on the current path. You need the gray/black coloring for directed cycle detection.