Graph Patterns for Coding Interviews: BFS, DFS, Topological Sort, and Union-Find

Feb 19, 202611 min read

Graph problems appear in nearly every coding interview. The key is knowing which pattern to apply: BFS for shortest path, DFS for connected components, topological sort for dependency ordering, and union-find for dynamic connectivity. This guide covers when to use each, code templates, common problems, and a decision framework.

When to Use Each Pattern

BFS

Use BFS when you need the shortest path in an unweighted graph, level-order traversal, or minimum steps to reach a target. It explores layer by layer using a queue.

DFS

Use DFS when you need connected components, path existence, cycle detection, or exhaustive exploration. It goes deep first using a stack or recursion.

Topological Sort

Use topological sort when you have a DAG and need a valid ordering of nodes respecting dependencies. Course prerequisites, build order, and task scheduling are classic uses.

Union-Find

Use union-find when you need to merge sets and answer connectivity queries efficiently. Number of islands with dynamic updates, Kruskal's MST, and detecting cycles in undirected graphs.

Code Templates

BFS Template

function bfs(start: number, graph: number[][]): number {
  const queue: number[] = [start];
  const visited = new Set([start]);
  let distance = 0;

  while (queue.length > 0) {
    const levelSize = queue.length;
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      if (isTarget(node)) return distance;
      for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    distance++;
  }
  return -1;
}

DFS Template

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

function countComponents(graph: number[][]): number {
  const visited = new Set<number>();
  let count = 0;
  for (let i = 0; i < graph.length; i++) {
    if (!visited.has(i)) {
      dfs(i, graph, visited);
      count++;
    }
  }
  return count;
}

Topological Sort (DFS)

function topologicalSort(graph: number[][]): number[] {
  const visited = new Set<number>();
  const result: number[] = [];

  function dfs(node: number): void {
    visited.add(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) dfs(neighbor);
    }
    result.push(node);
  }

  for (let i = 0; i < graph.length; i++) {
    if (!visited.has(i)) dfs(i);
  }
  return result.reverse();
}

Union-Find Template

class UnionFind {
  private parent: number[];
  private rank: number[];

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = Array(n).fill(0);
  }

  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x: number, y: number): void {
    const px = this.find(x);
    const py = this.find(y);
    if (px === py) return;
    if (this.rank[px] < this.rank[py]) this.parent[px] = py;
    else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
    else {
      this.parent[py] = px;
      this.rank[px]++;
    }
  }
}

Common Problems by Pattern

BFS

Word Ladder, Binary Tree Level Order Traversal, Rotting Oranges, 01 Matrix, Shortest Path in Binary Matrix

DFS

Number of Islands, Max Area of Island, Path Sum, Clone Graph, Pacific Atlantic Water Flow

Topological Sort

Course Schedule, Course Schedule II, Alien Dictionary, Sequence Reconstruction

Union-Find

Number of Connected Components, Redundant Connection, Accounts Merge, Number of Islands II (dynamic)

Decision Framework

Need shortest path or minimum steps? → BFS

Need level-order traversal? → BFS

Need connected components or path existence? → DFS (or BFS)

Need cycle detection in directed graph? → DFS with three-color marking

Need valid ordering respecting dependencies? → Topological Sort

Need to merge sets or answer connectivity as edges are added? → Union-Find

Is the graph a grid with adjacency by cell neighbors? → BFS or DFS (both work for traversal)

Pattern Links

Explore our interactive walkthroughs for each pattern:

Test your graph pattern recognition

Can you identify whether a problem needs BFS, DFS, topological sort, or union-find? Take our pattern recognition quiz.

Take the Quiz