Graphs: visit neighbours, remember who you've seen

A graph is a set of nodes joined by edges. Almost every graph problem is “start somewhere, visit the neighbours, and remember who you've visited so you never go round in circles”. The main choice is the order. Use breadth-first for the fewest steps, and depth-first to explore everything you can reach.

Think of it like this: passing news through friends. You tell your friends, and they tell theirs. Everyone keeps a list of who has already heard, so nobody is told twice. The first round of calls reaches everyone one step away. The second round reaches everyone two steps away. That's breadth-first.

How to spot it

Words and constraints in a problem that point to this pattern:

• Things connected to other things: “friends”, “flights between cities”, “roads”, “links”
• A 2D grid of '1' / '0' or '#' / '.' where you move up, down, left and right
• “Fewest steps” or “shortest path” when every move costs the same: breadth-first
• “How many groups / islands / connected regions?”: start a search from every unvisited node
• “Prerequisites”, “depends on”, “must come before”, “build order”: topological order

Watch it work

The template

// Build an adjacency list from a list of edges.
function buildGraph(edges: [string, string][]): Map<string, string[]> {
  const graph = new Map<string, string[]>();
  for (const [a, b] of edges) {
    if (!graph.has(a)) graph.set(a, []);
    if (!graph.has(b)) graph.set(b, []);
    graph.get(a)!.push(b);   // a → b
    graph.get(b)!.push(a);   // b → a too, because this graph is undirected (drop for one-way edges)
  }
  return graph;
}

// BFS: the fewest edges from start to goal, or -1 if goal can't be reached.
function fewestSteps(graph: Map<string, string[]>, start: string, goal: string): number {
  const visited = new Set<string>([start]);  // mark on ENQUEUE, so nothing is queued twice
  let queue: string[] = [start];             // every node at the current distance
  let steps = 0;
  while (queue.length > 0) {
    const next: string[] = [];               // every node one step further away
    for (const node of queue) {
      if (node === goal) return steps;       // first time we reach it = fewest steps
      for (const nb of graph.get(node) ?? []) {
        if (!visited.has(nb)) {
          visited.add(nb);
          next.push(nb);
        }
      }
    }
    queue = next;
    steps++;
  }
  return -1;
}

// DFS: visit everything reachable from node.
function dfs(graph: Map<string, string[]>, node: string, visited: Set<string>): void {
  if (visited.has(node)) return;   // already explored: stop here, or a cycle loops forever
  visited.add(node);
  for (const nb of graph.get(node) ?? []) dfs(graph, nb, visited);
}

// Grids: cell [r, c] is a node, and these are the moves to its 4 neighbours.
const DIRS: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]]; // down, up, right, left
// For each move: const nr = r + dr, nc = c + dc; skip it if off the grid, a wall, or visited.

// Topological order (Kahn's algorithm). An edge [b, a] means "b must come before a".
// Returns [] when there's a cycle, because then no valid order exists.
function topoOrder(nodes: string[], edges: [string, string][]): string[] {
  const waitingOn = new Map<string, string[]>(); // b → the nodes that wait for b
  const inDegree = new Map<string, number>();    // how many nodes each node still waits for
  for (const n of nodes) {
    waitingOn.set(n, []);
    inDegree.set(n, 0);
  }
  for (const [b, a] of edges) {
    waitingOn.get(b)!.push(a);
    inDegree.set(a, inDegree.get(a)! + 1);
  }
  const ready = nodes.filter((n) => inDegree.get(n) === 0); // nothing to wait for
  const order: string[] = [];
  for (let i = 0; i < ready.length; i++) {       // ready grows as we go; i walks it like a queue
    const n = ready[i];
    order.push(n);
    for (const a of waitingOn.get(n)!) {
      inDegree.set(a, inDegree.get(a)! - 1);     // one fewer thing to wait for
      if (inDegree.get(a) === 0) ready.push(a);  // everything a needed is placed
    }
  }
  return order.length === nodes.length ? order : []; // leftovers wait on each other: a cycle
}

Worked example

1. The first idea: try every possible route with recursion and keep the shortest. The number of routes explodes. An open 10 × 10 grid has tens of thousands of routes that only move right and down. There are far more once routes can turn back. This is too slow.

2. Notice two things. Every move costs the same, 1, and the question is “fewest moves”. That's exactly what BFS answers. It reaches cells in order of distance, so the first time it reaches the target, that distance is the answer. Each cell is processed at most once.

3. Name the graph: each cell [r, c] is a node, and its neighbours are the four cells around it. A neighbour is skipped if it's off the grid, a wall, or already visited. Store visited cells as strings like "1,2", because two different arrays [1, 2] are never equal in a Set.

4. Write BFS one level at a time, counting the levels as steps.

   function shortestPath(grid: string[][]): number {
     const rows = grid.length;
     const cols = grid[0].length;
     if (grid[0][0] === "#" || grid[rows - 1][cols - 1] === "#") return -1;
     const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
     const visited = new Set<string>(["0,0"]);
     let queue: [number, number][] = [[0, 0]];
     let steps = 0;
     while (queue.length > 0) {
       const next: [number, number][] = [];
       for (const [r, c] of queue) {
         if (r === rows - 1 && c === cols - 1) return steps; // reached the target
         for (const [dr, dc] of dirs) {
           const nr = r + dr;
           const nc = c + dc;
           if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; // off the grid
           if (grid[nr][nc] === "#") continue;                         // a wall
           const key = nr + "," + nc;
           if (visited.has(key)) continue;                              // already queued
           visited.add(key);
           next.push([nr, nc]);
         }
       }
       queue = next;
       steps++;
     }
     return -1; // the queue ran dry: the target is walled off
   }
   

5. Check it. Step 0 is [0,0]. Step 1 reaches [0,1]. Step 2 reaches [1,1]. Step 3 reaches [1,2] and [2,1]. Step 4 reaches [2,2], the target. Answer 4. Edge cases: a 1 × 1 open grid returns 0 straight away, and a target sealed off by walls empties the queue and returns -1.

Common mistakes

• Leaving out the visited set: in any graph with a loop the search never ends, and on a grid it bounces between two cells forever.
• Marking a node visited when it leaves the queue instead of when it enters: the same node is queued many times, and on a big grid the queue explodes.
• Storing grid cells in a Set as arrays: visited.has([1, 2]) is always false, because two arrays are never the same object. Use a string key like r + ',' + c.
• Using DFS for “fewest steps”: depth-first finds a path, often a long one. Only BFS guarantees the shortest when every step costs the same.
• In Kahn's algorithm, forgetting nodes that have no edges at all: they start with in-degree 0 and belong in the ready list. If you miss them, the order comes out too short and looks like a cycle.

Cost

In interviews