Graphs: BFS, DFS and topological sort

Graphs are the most general structure in this series: a linked list, a tree and a grid are all special cases. Networks, maps, dependency systems and social relationships are graphs, and once you can spot the graph hiding inside a problem, a surprising number of "hard" questions become one of four standard moves.

The problem it solves

Some relationships are not a line and not a hierarchy. A person can know many people who know each other. A city connects to several others by roads that form loops. A package depends on packages that share dependencies. You cannot store that as a list (there is no order) or a tree (there are cycles, and a node can have several parents).

A graph stores exactly what is there: nodes (also called vertices) and edges saying which pairs are connected. The interesting questions are all about paths and groups:

• Is there a route from A to B? What is the shortest one?
• How many separate groups exist? Are these two things connected?
• In what order can I do tasks that depend on each other?
• Can I visit everything reachable from here?

Structure: how to store a graph

The standard encodings trade memory for lookup speed.

Almost every interview graph is an adjacency list. Two properties to state before you code:

• Directed or undirected. An undirected edge is stored in both directions (A: [B] and B: [A]). A directed edge (a follow, a dependency) is stored once.
• Weighted or not. Weighted graphs attach a cost to each edge and need different algorithms for shortest paths.

function buildGraph(edges) {
  const adj = new Map();
  for (const [u, v] of edges) {
    if (!adj.has(u)) adj.set(u, []);
    if (!adj.has(v)) adj.set(v, []);
    adj.get(u).push(v);
    adj.get(v).push(u);     // drop this line for a directed graph
  }
  return adj;
}

BFS: shortest path in an unweighted graph

Breadth-first search is the tree traversal from the previous page, generalised. Visit the start node, then everything one edge away, then everything two edges away, and so on. A queue guarantees that you finish one distance before starting the next.

function shortestPath(adj, source, target) {
  if (source === target) return 0;
  const visited = new Set([source]);
  const queue = [[source, 0]];             // [node, distance]
  for (let head = 0; head < queue.length; head++) {
    const [node, dist] = queue[head];      // a head index avoids O(n) shift()
    for (const neighbor of adj.get(node) ?? []) {
      if (neighbor === target) return dist + 1;
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, dist + 1]);
      }
    }
  }
  return -1;                               // unreachable
}

Because BFS explores in strict distance order, the first time it reaches the target is guaranteed to be by a shortest path: everything closer was already visited. That guarantee only holds when every edge counts the same. For weighted edges you need Dijkstra's algorithm, which is BFS with a min-heap in place of a plain queue, so "closest known distance" replaces "arrived earliest".

The visited set is what stops a graph with cycles from looping forever. Mark a node visited when you enqueue it, not when you dequeue it, or the same node can be queued many times.

Cost: O(V + E) time (every node once, every edge once) and O(V) space.

DFS: go deep, then back up

Depth-first search follows one path as far as it goes before backing up. It uses a stack, either your own or the call stack through recursion. It does not give shortest paths, but it is the simplest way to answer "what is reachable?", "is there a cycle?" and "how many separate pieces are there?".

The graph you do not have to build: grids

A 2D grid is a graph in disguise. Every cell is a node, and its four neighbours (up, down, left, right) are its edges. You never build an adjacency list: you compute the neighbours from the coordinates.

1 1 0 0
1 0 0 1      two islands: the top-left group and the bottom-right group
0 0 1 1

function countIslands(grid) {
  const rows = grid.length;
  const cols = rows ? grid[0].length : 0;
  const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
  let islands = 0;

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== 1 || seen[r][c]) continue;
      islands++;                                  // a new, unvisited island
      const stack = [[r, c]];                     // flood fill it (iterative DFS)
      seen[r][c] = true;
      while (stack.length) {
        const [y, x] = stack.pop();
        for (const [dy, dx] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
          const ny = y + dy, nx = x + dx;
          if (ny < 0 || nx < 0 || ny >= rows || nx >= cols) continue;
          if (grid[ny][nx] !== 1 || seen[ny][nx]) continue;
          seen[ny][nx] = true;
          stack.push([ny, nx]);
        }
      }
    }
  }
  return islands;
}

Swap the stack for a queue and the same code gives shortest paths through a maze. Flood fill in a paint program, region counting, minesweeper reveals and "surrounded regions" are all this template.

A tree is just a graph with no cycles

Every tree is a graph: connected, with exactly one path between any two nodes. That is why level-order tree traversal and graph BFS are the same algorithm. A tree simply never needs the visited set, because there is no cycle to loop back through. The moment a node can be reached by two routes, you need to remember where you have been.

Topological sort: ordering dependencies

A directed graph with no cycles (a DAG) describes "A must happen before B". A topological order lists the nodes so that every edge points forward. This is what a build system, a package manager, a course planner or a spreadsheet's recalculation does.

The standard method is Kahn's algorithm, and it is BFS driven by in-degree (how many unfinished prerequisites a node still has):

1. Count the in-degree of every node.
2. Put every node with in-degree 0 into the queue: nothing blocks them.
3. Take one, output it, and decrement the in-degree of each node it points to. Any that reach 0 join the queue.
4. If you output fewer nodes than the graph has, the rest are on a cycle: no valid order exists.

function topoOrder(n, edges) {            // nodes 0..n-1, edge [a, b] means a before b
  const next = Array.from({ length: n }, () => []);
  const inDegree = new Array(n).fill(0);
  for (const [a, b] of edges) { next[a].push(b); inDegree[b]++; }

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

  const order = [];
  for (let head = 0; head < queue.length; head++) {
    const node = queue[head];
    order.push(node);
    for (const dep of next[node]) if (--inDegree[dep] === 0) queue.push(dep);
  }
  return order.length === n ? order : null;   // null means a cycle
}

Processing one whole layer at a time (as the diagram does) also answers "what is the minimum number of rounds if independent tasks run in parallel?", which is the number of layers. O(V + E) again.

Union-find: when you do not need the whole graph

Sometimes the question is not "what is the path" but just "are these connected at all?", or "how many groups are there?", and building and walking a full adjacency structure is more machinery than needed. Union-find (disjoint set) answers connectivity directly. Every node starts as its own group, and each edge merges two groups.

• find(x) returns the representative (the root) of x's group.
• union(x, y) merges the groups of x and y.
• x and y are connected exactly when find(x) === find(y).

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank   = new Array(n).fill(0);
    this.groups = n;
  }
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);   // path compression
    }
    return this.parent[x];
  }
  union(x, y) {
    const rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false;                     // already together
    if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
    else if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx;
    else { this.parent[ry] = rx; this.rank[rx]++; }  // union by rank
    this.groups--;
    return true;
  }
}

Path compression flattens the chain every time find walks it, so later lookups on the same node are nearly instant. Union by rank always hangs the shorter tree under the taller one, so trees stay flat. Together they make each operation amortised O(α(n)), the inverse Ackermann function, which stays below 5 for any input that fits in memory: effectively constant.

A useful side effect: union returns false when both nodes are already in the same group. That is exactly how you detect a cycle while adding edges one by one (Kruskal's minimum spanning tree relies on it).

Which tool for which question

Where graphs are used in real systems

Graphs you already use

• `npm install` and `pnpm`. They resolve a dependency graph and install in topological order. A circular dependency is a cycle.
• Git. Commits form a directed acyclic graph, and git merge-base is a graph search.
• The DOM. A tree, so also a graph, and event bubbling walks its parent edges.
• React and Excel-style dataflow. Derived values form a dependency graph that recalculates in dependency order.
• Webpack, Vite and TypeScript's module graph. Imports are edges, and tree-shaking is reachability from the entry points.
• Database query planners treat joins as a graph of tables when choosing an order.

When not to use a graph

• The data is really a list or a tree. A tree needs no visited set and simpler algorithms. Do not reach for graph machinery when the structure has no cycles.
• You only need pairwise lookups. If the question is "are A and B directly related?", a hash set of pairs is enough.
• A matrix on a huge sparse graph. An n by n matrix for a million nodes is a trillion cells. Use an adjacency list.
• BFS on a weighted graph. It returns the path with the fewest edges, not the lowest cost. Use Dijkstra.
• Recursive DFS on a huge grid. It can overflow the call stack. Use an explicit stack.

What interviewers ask

• "How would you represent this graph?" Adjacency list, and why. Ask whether it is directed and weighted.
• "Shortest path between two nodes." BFS if unweighted (say why the first hit is shortest), Dijkstra if weighted.
• "Number of islands, or connected components." DFS or BFS flood fill on a grid, or union-find.
• "Detect a cycle." DFS with three states (unvisited, in progress, done) for directed graphs; union-find for undirected.
• "Course schedule, build order, alien dictionary." Topological sort, and returning -1 or false when there is a cycle.
• "BFS versus DFS?" The table above, and the memory trade-off.
• "Why is union-find nearly O(1)?" Path compression plus union by rank.
• "What is the complexity of BFS?" O(V + E), and why it is not O(V squared).
• "Clone a graph." A hash map from old node to new node, which doubles as the visited set.

The mistake to avoid

Forgetting the visited set, or marking nodes visited too late. On a graph with a cycle, a missing visited set loops forever. Marking on dequeue instead of enqueue lets the same node enter the queue many times, which turns O(V + E) into something much worse and can blow up memory. Mark a node the moment you queue it, and only ever queue unvisited nodes.

If a problem mentions "connected", "reachable", "path", "dependency", "groups" or a grid of cells, ask yourself what the nodes and the edges are. Once you can name them, the rest is choosing between BFS, DFS, topological sort and union-find.