133. Clone Graph

Given a node in a connected undirected graph (as an adjacency list where node i+1's neighbors are adjList[i]), return a deep copy of the graph.

Clone the start node, then BFS. When a neighbor is first seen, clone it and enqueue it. Always wire the edge from the current copy.

1function cloneGraph(node: _Node | null): _Node | null {
2  if (!node) return null;
3  const clones = new Map([[node, new _Node(node.val)]]);
4  const queue = [node];
5  while (queue.length) {
6    const n = queue.shift()!;
7    for (const nb of n.neighbors) {
8      if (!clones.has(nb)) { clones.set(nb, new _Node(nb.val)); queue.push(nb); }
9      clones.get(n)!.neighbors.push(clones.get(nb)!);
10    }
11  }
12  return clones.get(node)!;
13}

original

clone

old → new

11'

queue

Clone node 1 and enqueue it.

1 / 0

Space: play/pause · ←/→: step