Graphs: representation & traversal

A graph is nodes plus connections, nothing more

Trees have exactly one root and no cycles. A graph relaxes both: any node can connect to any other node, connections can be one-way (directed) or two-way (undirected), and cycles are allowed. That generality is why graphs model almost anything — social networks, road maps, dependency chains, web pages linking to each other.

Two ways to store one, and when each wins

// building an adjacency list from an edge list — the shape you'll write constantly
function buildGraph(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u); // omit this line for a DIRECTED graph
  }
  return graph;
}

Weighted, directed and labelled graphs

The adjacency list above is the shape you want to work in, but problems rarely hand it to you that way. Three inputs turn up again and again, and the first move in every solution is to convert the input into a form where "give me the neighbours of x" is one lookup.

Weights

If an edge carries a number, a distance, cost or probability, store that number next to the neighbour. In a list each entry becomes a pair [neighbour, weight]. In a matrix each cell holds the weight instead of 1, and "no edge" needs a value that cannot be a real weight. 0 is a poor choice, because a free edge is legal in many problems; Infinity works with Math.min.

function buildWeighted(n, edges, directed = false) {
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) {
    graph[u].push([v, w]); // every entry is [neighbour, weight]
    if (!directed && u !== v) graph[v].push([u, w]); // an undirected edge is stored from both ends
  }
  return graph;
}

A directed graph stores the edge once, at u. An undirected graph stores it at both ends, so every edge appears twice in the lists: the total list length is 2E for E undirected edges, while "E" in O(V + E) still counts each edge once. A self-loop [u, u] would be pushed twice onto the same list if we did not guard, which is the reason for the u !== v test.

Converting back and forth

Sometimes the algorithm wants a different shape than the input. Edge-list algorithms (Kruskal's minimum spanning tree, for example) want the list of edges, and Floyd–Warshall wants a matrix. These conversions are short and worth being able to write without thinking.

function listToEdges(graph, directed = false) {
  const edges = [];
  graph.forEach((neighbours, u) => {
    for (const [v, w] of neighbours) {
      if (directed || u <= v) edges.push([u, v, w]); // undirected: report each edge once
    }
  });
  return edges;
}

function listToMatrix(graph) {
  const n = graph.length;
  const matrix = Array.from({ length: n }, () => new Array(n).fill(Infinity)); // Infinity = no edge
  graph.forEach((neighbours, u) => {
    for (const [v, w] of neighbours) matrix[u][v] = Math.min(matrix[u][v], w); // a matrix holds one weight per pair
  });
  return matrix;
}

function matrixToList(matrix) {
  return matrix.map((row) => {
    const neighbours = [];
    row.forEach((w, v) => {
      if (w !== Infinity) neighbours.push([v, w]);
    });
    return neighbours;
  });
}

listToEdges keeps an undirected edge only from its smaller end (u <= v), so each one comes out once. listToMatrix is O(V²) in space whatever the edge count, and a matrix has one cell per pair, so two parallel edges between the same pair are squeezed into one cell, keeping the cheaper. Going list to edges and back to a list gives the same edges. We checked these four functions by converting thousands of random graphs, with parallel edges and self-loops, back and forth and comparing the edges.

Labels that are not numbers

When nodes are names (words, city codes, variables in an equation) use a Map from the label to its neighbour array. Do not use a plain object: object keys are always strings, so a node labelled with the number 1 is stored under "1", and the check visited.has(1) is then false for a visited set that holds "1". We tried it: new Set([1]).has("1") is false.

function buildLabelled(nodes, edges) {
  const graph = new Map();
  for (const node of nodes) graph.set(node, []); // isolated nodes only exist because we list them here
  for (const [u, v] of edges) {
    graph.get(u).push(v);
    graph.get(v).push(u);
  }
  return graph;
}

The first loop is not decoration. An edge list can only mention nodes that have at least one edge, so a node with no edges would never appear in the map and its component would be missed. If the statement gives the node list or a count n, build from that, not from the edges.

DFS — go deep, backtrack when stuck

// recursive DFS — the call stack IS the "backtrack" mechanism, for free
function dfs(graph, start, visited = new Set()) {
  visited.add(start);
  console.log(start);
  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) dfs(graph, neighbor, visited);
  }
  return visited;
}

// iterative DFS — an explicit stack instead of recursion; reaches the same nodes, but not always in the same order
function dfsIterative(graph, start) {
  const visited = new Set([start]);
  const stack = [start];
  while (stack.length) {
    const node = stack.pop();
    console.log(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        stack.push(neighbor);
      }
    }
  }
  return visited;
}

Both visit exactly the same set of nodes, but the order can differ. On the diamond 0:[1,2], 1:[3], 2:[3] the recursive version prints 0, 1, 3, 2, while the iterative one pushes 1 then 2 and pops 2 first, so it prints 0, 2, 3, 1. Both are valid depth-first orders. To get the recursive order exactly, mark a node visited when you pop it (skipping it if it is already visited) and push its neighbours in reverse, as the demo below does.

DFS and the call stack: when recursion runs out

Recursive DFS is short and easy to read, and it has one hidden cost: every active call holds a frame on the call stack until it returns. When DFS dives down a path, the number of frames alive at once equals the length of the path it is on. On a graph that is one long chain, a linked list that is also a graph, a one-row grid, or a tree that has leaned to one side, that path has V nodes. The work is still O(V + E), but the stack is V frames deep, and the stack is a small fixed-size area, not the whole heap.

The failure is easy to see. We ran the chapter's recursive dfs in Node 24 over a chain 0 → 1 → 2 → .... A chain of 3,000 nodes finished, and a chain of 10,000 nodes threw RangeError: Maximum call stack size exceeded. The point where it breaks depends on the engine, the size of each frame and the stack that is available (it also moves with how warm the code is), so do not memorise a number: remember that it is thousands, not hundreds of thousands.

Turn the recursion into data

A recursive call remembers two things: which node it is working on, and how far through its neighbour loop it has got. If you store exactly that, a pair [node, index of the next neighbour] per call, on your own array, you have the call stack as data, and the array lives on the heap, so its size is limited by memory, not by the stack. The single-stack-of-nodes version earlier in the chapter loses the loop position, and with it the exact recursive order and any chance to act when a call returns. The frame version keeps all three.

function dfsIterative(graph, start) {
  const visited = new Set([start]);
  const order = [start];
  const stack = [[start, 0]]; // [node, index of the next neighbour to try]
  while (stack.length > 0) {
    const frame = stack[stack.length - 1];
    const [node, i] = frame;
    if (i === graph[node].length) {
      stack.pop(); // every neighbour tried: this is where the recursive call would return
      continue;
    }
    frame[1]++;
    const next = graph[node][i];
    if (!visited.has(next)) {
      visited.add(next);
      order.push(next);
      stack.push([next, 0]); // this is the recursive call
    }
  }
  return order;
}

Dry run: dfsIterative on 0:[1, 2], 1:[3], 2:[3], 3:[]

The order 0, 1, 3, 2 is the one the recursive version gave in the earlier example, where the one-stack version printed 0, 2, 3, 1. Steps 3, 4, 7 and 8 are the moments a recursive call would return. If a problem needs something done after all of a node's neighbours (a post-order action, such as computing a subtree size or marking a node "done" in cycle detection), that is where it goes. Cost: O(V + E) time, and the stack of frames holds at most V entries. We compared its order with the recursive one on thousands of random graphs, and ran it on a chain of 200,000 nodes, which the recursive version cannot do.

Two other ways out. If the visiting order does not matter and you only need "what is reachable", BFS never recurses and has no such limit. And in an interview you rarely need to code the frame version unless the constraints force it: naming the limit and saying which of these two you would switch to is usually enough.

BFS — spread outward, layer by layer

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);   // mark visited when ENQUEUED, not when dequeued
        queue.push(neighbor);
      }
    }
  }
  return order;
}

Dry run: bfs(graph, "A") on the five-node graph above

Visit order: A, B, D, C, E. D gets enqueued at step 1 even though it's processed after B and before C — that's the queue's FIFO order at work, not the order neighbors were listed in.

BFS with distances, and the path itself

The BFS above only lists nodes in visiting order. Most problems ask for something more: how many edges to reach a node, or which edges to take. Both come from a small change to the same loop, because of one fact: the node that first reaches next is node, which sits one layer closer to the source. So the distance of next is the distance of node plus one, and the parent of next is node. Set both at the moment you enqueue, the same moment you would mark it visited.

function bfsDistances(graph, source) {
  const dist = new Array(graph.length).fill(-1); // -1 means "not reached yet"
  dist[source] = 0;
  const queue = [source];
  for (let head = 0; head < queue.length; head++) {
    const node = queue[head];
    for (const next of graph[node]) {
      if (dist[next] === -1) {
        dist[next] = dist[node] + 1; // one edge further than the node that found it
        queue.push(next);
      }
    }
  }
  return dist;
}

The distance array does double duty. -1 means "not seen", so it replaces the visited set, and anything still -1 at the end is unreachable from the source. Time O(V + E), space O(V). The queue uses a moving head index in place of shift(): an array used as a queue with shift() can cost O(n) per removal on a long array, which would make the loop quadratic, whereas the head index makes each removal O(1) and keeps the array as a log of visited nodes.

To get the path, record who found each node. Following those parent links from the target back to the source gives the path in reverse.

function shortestPath(graph, source, target) {
  const parent = new Array(graph.length).fill(-2); // -2 = unseen, -1 = the source has no parent
  parent[source] = -1;
  const queue = [source];
  for (let head = 0; head < queue.length && parent[target] === -2; head++) {
    const node = queue[head];
    for (const next of graph[node]) {
      if (parent[next] === -2) {
        parent[next] = node; // remember who discovered it
        queue.push(next);
      }
    }
  }
  if (parent[target] === -2) return null; // never reached
  const path = [];
  for (let at = target; at !== -1; at = parent[at]) path.push(at); // walk back from the target
  return path.reverse();
}

Dry run: shortestPath(graph, A, C) on the five-node graph, with A to E as 0 to 4

The adjacency lists are A:[B, D], B:[A, C, E], C:[B, E], D:[A, E], E:[B, C, D]. The loop stops as soon as the target has a parent.

Walking back from C: C's parent is B, B's parent is A, A's parent is -1, so the reversed list is [A, B, C], which has two edges, matching distance 2. Notice that E also has distance 2 (through B) even though the loop stopped before processing it.

We checked bfsDistances and shortestPath against a plain relaxation search on thousands of random directed and undirected graphs: the distances matched, and every returned path starts at the source, ends at the target, uses real edges and has exactly the shortest length.

Watch both traversals

Disconnected graphs: the outer loop

Everything above grows from one start node, so it can only reach that node's component, the set of nodes joined to it by some path. If the graph falls into several pieces, one traversal sees one piece. Any problem about the whole graph ("visit everything", "count the pieces", "is there a cycle anywhere") therefore needs a loop around the traversal: try every node as a start, and skip the ones already reached.

function componentLabels(graph) {
  const label = new Array(graph.length).fill(-1);
  let count = 0;
  for (let start = 0; start < graph.length; start++) {
    if (label[start] !== -1) continue; // an earlier start already reached it
    label[start] = count;
    const queue = [start];
    for (let head = 0; head < queue.length; head++) {
      for (const next of graph[queue[head]]) {
        if (label[next] === -1) {
          label[next] = count;
          queue.push(next);
        }
      }
    }
    count++;
  }
  return { label, count };
}

Dry run: 6 nodes, edges 0-1, 1-2, 3-4, node 5 alone

The result is label = [0, 0, 0, 1, 1, 2] and count = 3. The traversal inside the loop starts at most once per node and looks at each edge a constant number of times in total, so the loop does not multiply the cost: the whole function is O(V + E), with O(V) space. A graph is connected exactly when count is 1. Checked on thousands of random graphs against a union-find count, and every edge joins two nodes with the same label.

DFS vs BFS — the complexity is identical, the use case isn't

Clone graph: copying a structure that has cycles

Given one node of a connected undirected graph, build a deep copy: new node objects with the same values and the same connections, sharing nothing with the original. Copying a tree is a simple recursion: copy the node, copy each child. On a graph that same recursion never ends, because a node's neighbour has that node as its neighbour, so the copy of A asks for a copy of B, which asks for a copy of A, and so on.

The fix is the same one that makes DFS finish: remember what you have already done. But here "done" is not enough, because you must also be able to get the copy back when you meet the node again, so the Set of visited nodes becomes a Map from each original to its copy. The one rule that matters is when you write to it: before you recurse into the neighbours, not after.

class GraphNode {
  constructor(val) {
    this.val = val;
    this.neighbors = [];
  }
}

function cloneGraph(node) {
  if (node === null) return null;
  const copies = new Map(); // original node -> its copy
  function copy(original) {
    if (copies.has(original)) return copies.get(original);
    const clone = new GraphNode(original.val);
    copies.set(original, clone); // register BEFORE visiting neighbours: this is what stops a cycle
    for (const neighbor of original.neighbors) clone.neighbors.push(copy(neighbor));
    return clone;
  }
  return copy(node);
}

Dry run: the four-node cycle 1-2-3-4-1, called on node 1

Every node is created once, and every edge is followed once from each end, so the time is O(V + E) and the map and the recursion use O(V) space. The recursion depth is up to V, so the warning about call stacks applies here too: with a very long chain the same algorithm needs a BFS or an explicit stack. We tested it on thousands of random graphs, including self-loops, checking that the copy has the same shape, that no node object is shared with the original, and that every neighbour of a copy is itself a copy.

The idea behind it is wider than this one problem. When a traversal must produce a result for every node (a copy, a label, a distance), the visited set grows into a map from node to result, and you fill the entry before going deeper. You have just seen it three times: the distance array, the label array, and the copy map.

A grid is a graph you never build

A grid problem hands you no edge list, but it is a graph all the same: each cell is a node, and two cells are joined when you can step from one to the other. You do not need to build an adjacency list. A cell's neighbours are computed on the spot from its row and column, and a cell is recorded as visited in a second grid, a set of strings or a set of numbers such as row * columns + column. A graph whose edges are computed rather than stored is an implicit graph, and everything in this chapter (the queue, the distances, the visited marking on enqueue) works on it unchanged.

The details of grids, the four-direction arrays, the boundary checks, flood fill, several sources at once and "reach from the border" problems, as well as searching over states that are not cells, such as word ladder, have their own chapter: BFS on grids and implicit graphs. The component-counting and cycle problems that sit on top of plain graphs are in Graph problems.

Recognizing it in an unseen problem

• Input described as nodes/edges, a grid (adjacent cells = edges), or "connections between X and Y"
• "Shortest path," "fewest steps," "minimum number of moves" on an unweighted graph → BFS
• "Does a path exist," "all paths," "explore every option" → DFS
• A 2D grid where you move up/down/left/right is a graph in disguise — each cell is a node, each valid move is an edge
• "How many edges," "what is the route," "print the path": BFS with a distance and a parent per node
• "How many groups," "is everything connected," "does a cycle exist anywhere": a traversal inside a loop over every node
• "Copy this structure" when nodes can point back at each other: a map from each original to its copy, filled before you recurse
• A chain, a deep tree or a huge all-land grid under a recursive DFS: say that the call stack may run out, and switch to an explicit stack or BFS