Graph Algorithms for Coding Interviews: Full Guide

Graph problems appear in roughly 30% of coding interviews at top tech companies, yet many candidates treat them as an afterthought. Graph algorithms are among the most versatile tools in your interview toolkit — once you master them, you can solve problems ranging from social networks to GPS navigation.

Graph Representation

Before solving problems, you need to know how to represent graphs in code. The two main approaches:

Adjacency List (Most Common in Interviews)

// Build adjacency list from edge list
function buildGraph(n: number, edges: number[][]): Map<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); // remove for directed graph
  }
  return graph;
}

Adjacency Matrix

Use when you need O(1) edge lookups or when the graph is dense. Less common in interviews.

// Build adjacency matrix
function buildMatrix(n: number, edges: number[][]): boolean[][] {
  const matrix = Array.from({ length: n }, () => new Array(n).fill(false));
  for (const [u, v] of edges) {
    matrix[u][v] = true;
    matrix[v][u] = true;
  }
  return matrix;
}

BFS — Breadth-First Search

When to use: Shortest path in unweighted graphs, level-order traversal, finding the nearest target.

BFS explores all nodes at distance K before moving to distance K+1. It uses a queue and guarantees the shortest path in unweighted graphs.

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

  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);
        queue.push(neighbor);
      }
    }
  }
  return order;
}

Classic problems: Shortest Path in Binary Matrix, Word Ladder, Rotting Oranges, 01 Matrix.

DFS — Depth-First Search

When to use: Connected components, cycle detection, path finding, topological sort, backtracking on graphs.

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

  function explore(node: number) {
    visited.add(node);
    order.push(node);
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        explore(neighbor);
      }
    }
  }

  explore(start);
  return order;
}

Classic problems: Number of Islands, Clone Graph, Pacific Atlantic Water Flow, Course Schedule.

Dijkstra's Algorithm — Weighted Shortest Path

When to use: Shortest path in weighted graphs with non-negative weights.

// Dijkstra using a min-heap (priority queue)
function dijkstra(graph: Map<number, [number, number][]>, start: number, n: number): number[] {
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;
  // [distance, node] — sorted by distance
  const pq: [number, number][] = [[0, start]];

  while (pq.length > 0) {
    pq.sort((a, b) => a[0] - b[0]);
    const [d, u] = pq.shift()!;
    if (d > dist[u]) continue;
    for (const [v, w] of graph.get(u) || []) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pq.push([dist[v], v]);
      }
    }
  }
  return dist;
}

Classic problems: Network Delay Time, Cheapest Flights Within K Stops, Path with Maximum Probability.

Topological Sort

When to use: Ordering tasks with dependencies, detecting cycles in directed graphs, build systems.

// Kahn's Algorithm (BFS-based topological sort)
function topologicalSort(n: number, edges: number[][]): number[] {
  const inDegree = new Array(n).fill(0);
  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);
    inDegree[v]++;
  }

  const queue: number[] = [];
  for (let i = 0; i < n; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const order: number[] = [];
  while (queue.length > 0) {
    const node = queue.shift()!;
    order.push(node);
    for (const neighbor of graph.get(node)!) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return order.length === n ? order : []; // empty = cycle exists
}

Classic problems: Course Schedule I & II, Alien Dictionary, Parallel Courses.

Union-Find (Disjoint Set Union)

When to use: Connected components, cycle detection in undirected graphs, grouping, Kruskal's MST.

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

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

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

  union(x: number, y: number): boolean {
    const px = this.find(x), py = this.find(y);
    if (px === py) return false; // already connected
    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]++; }
    return true;
  }
}

Classic problems: Number of Connected Components, Redundant Connection, Accounts Merge, Smallest String With Swaps.

Treating Grids as Graphs

Many interview problems present a 2D grid that is actually a graph problem in disguise. Each cell is a node, and adjacent cells (up, down, left, right) are edges.

// Standard 4-directional movement
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

function isValid(r: number, c: number, rows: number, cols: number): boolean {
  return r >= 0 && r < rows && c >= 0 && c < cols;
}

Classic grid-as-graph problems: Number of Islands, Flood Fill, Surrounded Regions, Walls and Gates.

How to Identify Graph Problems

• The problem mentions connections, relationships, or networks
• You need to find shortest path, connected components, or cycles
• The input is a 2D grid with traversal constraints
• Tasks have dependencies (topological sort signal)
• You need to group or merge items (union-find signal)

Practice Roadmap

1. Week 1: BFS and DFS fundamentals — Number of Islands, Clone Graph, Max Area of Island
2. Week 2: Shortest path — Word Ladder, Network Delay Time, Cheapest Flights
3. Week 3: Topological sort — Course Schedule I/II, Alien Dictionary
4. Week 4: Union-Find — Redundant Connection, Accounts Merge, Number of Provinces

Conclusion

Graph algorithms are essential for coding interviews at every top tech company. Master the five core techniques — BFS, DFS, Dijkstra, topological sort, and union-find — and you'll be equipped to handle any graph problem thrown at you. Combine this with the other essential LeetCode patterns and practice with mock interviews for the best results.

Need help while practicing? Try InterviewAlly free and get AI-powered real-time assistance during your coding sessions.