Graph Algorithms: BFS and DFS Explained

Understanding Graphs

A graph is a data structure consisting of nodes (also called vertices) connected by edges. Unlike trees, graphs can have cycles and nodes can have any number of connections. Graphs model relationships in social networks, road maps, dependencies, and countless other real-world scenarios.

Before diving into traversal algorithms, you need to understand how to represent graphs in code. The two most common representations are adjacency lists and adjacency matrices.

Graph Representations

Adjacency List

An adjacency list stores, for each node, a list of its neighbors. This is the most common representation for sparse graphs (graphs with relatively few edges).

// Adjacency list using a Map
type Graph = Map<number, number[]>

function buildAdjacencyList(edges: number[][]): Graph {
  const graph: Graph = new Map()

  for (const [u, v] of edges) {
    // For undirected graph, add both directions
    if (!graph.has(u)) graph.set(u, [])
    if (!graph.has(v)) graph.set(v, [])

    graph.get(u)!.push(v)
    graph.get(v)!.push(u)  // Remove for directed graph
  }

  return graph
}

// Example: edges = [[0,1], [1,2], [2,0]]
// Creates: { 0: [1,2], 1: [0,2], 2: [1,0] }

Space: O(V + E) where V is vertices and E is edges
Best for: Sparse graphs, most interview problems

Adjacency Matrix

An adjacency matrix is a 2D array where matrix[i][j] indicates whether there's an edge from node i to node j. Good for dense graphs or when you need O(1) edge lookups.

// Adjacency matrix
function buildAdjacencyMatrix(n: number, edges: number[][]): number[][] {
  const matrix: number[][] = Array.from(
    { length: n },
    () => Array(n).fill(0)
  )

  for (const [u, v] of edges) {
    matrix[u][v] = 1
    matrix[v][u] = 1  // Remove for directed graph
  }

  return matrix
}

// Example: n=3, edges = [[0,1], [1,2]]
// Creates: [[0,1,0], [1,0,1], [0,1,0]]

Space: O(V^2)
Best for: Dense graphs, weighted edges, O(1) edge existence checks

Breadth-First Search (BFS)

BFS explores the graph level by level, visiting all neighbors at the current depth before moving to the next level. It uses a queue to maintain the order of exploration.

When to Use BFS

• Shortest path in unweighted graphs - BFS guarantees the shortest path
• Level-by-level processing - When you need to track distance from source
• Finding closest nodes - Nearest neighbor problems
• Traversing by layers - Like level-order tree traversal

BFS Implementation

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

  visited.add(start)

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

    // Process all neighbors
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor)
        queue.push(neighbor)
      }
    }
  }

  return result
}

// BFS with level tracking (useful for shortest path)
function bfsWithLevels(
  graph: Map<number, number[]>,
  start: number
): Map<number, number> {
  const distance = new Map<number, number>()
  const queue: number[] = [start]

  distance.set(start, 0)

  while (queue.length > 0) {
    const node = queue.shift()!
    const currentDist = distance.get(node)!

    for (const neighbor of graph.get(node) || []) {
      if (!distance.has(neighbor)) {
        distance.set(neighbor, currentDist + 1)
        queue.push(neighbor)
      }
    }
  }

  return distance  // distance.get(target) gives shortest path length
}

Time: O(V + E)
Space: O(V) for the queue and visited set

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses astack (or recursion, which implicitly uses the call stack) to track the path.

When to Use DFS

• Cycle detection - Tracking visited states along current path
• Topological sort - Ordering dependencies
• Connected components - Finding all nodes in a group
• Path finding - When any path works (not necessarily shortest)
• Exhaustive exploration - Backtracking problems

DFS Implementations

// Recursive DFS
function dfsRecursive(
  graph: Map<number, number[]>,
  start: number,
  visited = new Set<number>()
): number[] {
  const result: number[] = []

  function explore(node: number) {
    if (visited.has(node)) return

    visited.add(node)
    result.push(node)

    for (const neighbor of graph.get(node) || []) {
      explore(neighbor)
    }
  }

  explore(start)
  return result
}

// Iterative DFS using explicit stack
function dfsIterative(
  graph: Map<number, number[]>,
  start: number
): number[] {
  const visited = new Set<number>()
  const stack: number[] = [start]
  const result: number[] = []

  while (stack.length > 0) {
    const node = stack.pop()!

    if (visited.has(node)) continue

    visited.add(node)
    result.push(node)

    // Add neighbors to stack (reverse for same order as recursive)
    const neighbors = graph.get(node) || []
    for (let i = neighbors.length - 1; i >= 0; i--) {
      if (!visited.has(neighbors[i])) {
        stack.push(neighbors[i])
      }
    }
  }

  return result
}

Time: O(V + E)
Space: O(V) for visited set, O(H) for recursion stack where H is max depth

Cycle Detection with DFS

To detect cycles, we track nodes in the current DFS path. If we revisit a node that's already in our current path, we've found a cycle.

// Cycle detection in directed graph
function hasCycle(graph: Map<number, number[]>, n: number): boolean {
  const visited = new Set<number>()
  const inPath = new Set<number>()  // Nodes in current DFS path

  function dfs(node: number): boolean {
    if (inPath.has(node)) return true   // Cycle found
    if (visited.has(node)) return false // Already processed

    visited.add(node)
    inPath.add(node)

    for (const neighbor of graph.get(node) || []) {
      if (dfs(neighbor)) return true
    }

    inPath.delete(node)  // Backtrack
    return false
  }

  // Check all nodes (graph might be disconnected)
  for (let i = 0; i < n; i++) {
    if (dfs(i)) return true
  }

  return false
}

Topological Sort

Topological sort orders nodes in a directed acyclic graph (DAG) such that for every directed edge u → v, node u comes before v. Essential for dependency resolution.

// Topological sort using DFS
function topologicalSort(graph: Map<number, number[]>, n: number): number[] {
  const visited = new Set<number>()
  const result: number[] = []

  function dfs(node: number) {
    if (visited.has(node)) return
    visited.add(node)

    for (const neighbor of graph.get(node) || []) {
      dfs(neighbor)
    }

    // Add to front after processing all descendants
    result.unshift(node)
  }

  for (let i = 0; i < n; i++) {
    dfs(i)
  }

  return result
}

// Alternative: Kahn's algorithm using BFS (also detects cycles)
function topologicalSortBFS(
  graph: Map<number, number[]>,
  n: number
): number[] | null {
  // Calculate in-degrees
  const inDegree = new Array(n).fill(0)
  for (const neighbors of graph.values()) {
    for (const neighbor of neighbors) {
      inDegree[neighbor]++
    }
  }

  // Start with nodes that have no dependencies
  const queue: number[] = []
  for (let i = 0; i < n; i++) {
    if (inDegree[i] === 0) queue.push(i)
  }

  const result: number[] = []

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

    for (const neighbor of graph.get(node) || []) {
      inDegree[neighbor]--
      if (inDegree[neighbor] === 0) {
        queue.push(neighbor)
      }
    }
  }

  // If not all nodes processed, there's a cycle
  return result.length === n ? result : null
}

Classic Interview Problems

Problem 1: Number of Islands

Question: Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

function numIslands(grid: string[][]): number {
  if (grid.length === 0) return 0

  const rows = grid.length
  const cols = grid[0].length
  let count = 0

  function dfs(r: number, c: number) {
    // Boundary and water check
    if (r < 0 || r >= rows || c < 0 || c >= cols) return
    if (grid[r][c] !== '1') return

    // Mark as visited by changing to '0'
    grid[r][c] = '0'

    // Explore all 4 directions
    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') {
        count++
        dfs(r, c)  // Sink the entire island
      }
    }
  }

  return count
}

// Time: O(rows * cols), Space: O(rows * cols) for recursion stack

Problem 2: Clone Graph

Question: Given a reference to a node in a connected undirected graph, return a deep copy of the graph.

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

function cloneGraph(node: GraphNode | null): GraphNode | null {
  if (!node) return null

  // Map from original node to its clone
  const visited = new Map<GraphNode, GraphNode>()

  function dfs(original: GraphNode): GraphNode {
    // Return existing clone if already created
    if (visited.has(original)) {
      return visited.get(original)!
    }

    // Create clone (without neighbors initially)
    const clone = new GraphNode(original.val)
    visited.set(original, clone)

    // Clone all neighbors
    for (const neighbor of original.neighbors) {
      clone.neighbors.push(dfs(neighbor))
    }

    return clone
  }

  return dfs(node)
}

// Time: O(V + E), Space: O(V) for the map

Problem 3: Course Schedule

Question: There are n courses labeled 0 to n-1. Given prerequisites where [a, b] means you must take course b before course a, determine if you can finish all courses.

function canFinish(
  numCourses: number,
  prerequisites: number[][]
): boolean {
  // Build adjacency list
  const graph = new Map<number, number[]>()
  for (let i = 0; i < numCourses; i++) {
    graph.set(i, [])
  }
  for (const [course, prereq] of prerequisites) {
    graph.get(prereq)!.push(course)
  }

  // States: 0 = unvisited, 1 = visiting (in current path), 2 = visited
  const state = new Array(numCourses).fill(0)

  function hasCycle(course: number): boolean {
    if (state[course] === 1) return true  // Cycle detected
    if (state[course] === 2) return false // Already processed

    state[course] = 1  // Mark as visiting

    for (const next of graph.get(course)!) {
      if (hasCycle(next)) return true
    }

    state[course] = 2  // Mark as visited
    return false
  }

  // Check all courses for cycles
  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false
  }

  return true
}

// Time: O(V + E), Space: O(V + E)

Problem 4: Pacific Atlantic Water Flow

Question: Given an m x n matrix of heights, find all cells where water can flow to both the Pacific (top/left edges) and Atlantic (bottom/right edges) oceans.

function pacificAtlantic(heights: number[][]): number[][] {
  if (heights.length === 0) return []

  const rows = heights.length
  const cols = heights[0].length

  const pacific = new Set<string>()
  const atlantic = new Set<string>()

  // DFS from ocean toward higher ground
  function dfs(
    r: number,
    c: number,
    reachable: Set<string>,
    prevHeight: number
  ) {
    const key = `${r},${c}`

    // Boundary check
    if (r < 0 || r >= rows || c < 0 || c >= cols) return
    // Already visited
    if (reachable.has(key)) return
    // Water can't flow uphill (from ocean perspective)
    if (heights[r][c] < prevHeight) return

    reachable.add(key)

    const height = heights[r][c]
    dfs(r + 1, c, reachable, height)
    dfs(r - 1, c, reachable, height)
    dfs(r, c + 1, reachable, height)
    dfs(r, c - 1, reachable, height)
  }

  // Start DFS from Pacific edges (top and left)
  for (let c = 0; c < cols; c++) {
    dfs(0, c, pacific, 0)           // Top row
    dfs(rows - 1, c, atlantic, 0)   // Bottom row
  }
  for (let r = 0; r < rows; r++) {
    dfs(r, 0, pacific, 0)           // Left column
    dfs(r, cols - 1, atlantic, 0)   // Right column
  }

  // Find intersection - cells that reach both oceans
  const result: number[][] = []
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      const key = `${r},${c}`
      if (pacific.has(key) && atlantic.has(key)) {
        result.push([r, c])
      }
    }
  }

  return result
}

// Time: O(rows * cols), Space: O(rows * cols)

BFS vs DFS: Quick Decision Guide

Pro Tips

• Grid problems are graphs: Each cell is a node, neighbors are adjacent cells
• Mark visited early: Add to visited set before enqueueing/recursing to avoid duplicates
• Direction arrays: Use const dirs = [[0,1],[1,0],[0,-1],[-1,0]] for clean 4-direction movement
• Bidirectional BFS: For finding path between two nodes, search from both ends to halve the search space
• State encoding: For complex states, encode as strings for the visited set

Practice Problems

Ready to solidify your understanding? Try these problems:

• Easy: Flood Fill, Max Area of Island
• Medium: Number of Islands, Clone Graph, Course Schedule, Pacific Atlantic Water Flow, Word Ladder
• Hard: Word Ladder II, Alien Dictionary, Shortest Path in Binary Matrix

Continue Learning

• Dynamic Programming Guide — Often combined with graphs for optimization problems
• Binary Search Patterns — Another fundamental algorithm technique
• Two Pointers Pattern — Efficient array and string traversal
• Start Practicing — Apply graph algorithms to real interview problems