Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumgraph-dfs

Clone Graph

Problem (restated)

Given a reference to a node in a connected undirected graph, return a deep copy of the graph. Each node has a unique val and a list of neighbors. Cycles are expected.

Intuition

You cannot copy a node twice or you split the cycle. The first time you see an original node, allocate its clone and record original → clone. Then copy edges by looking neighbors up in that map. The map is the visited set.

Approaches

DFS with clone map

Unverified

Time O(V+E)Space O(V)

Idea. clones: Map<Node, Node>. On visit: if already cloned, return it; else create the copy, insert into the map before recursing (so a back-edge finds it), then append dfs(neighbor) onto copy.neighbors.

Walkthrough. Four-node cycle 1—2—3—4—1. First DFS allocates 1 then 2; the edge back to 1 hits the map instead of allocating again.

Trade-offs. Natural graph-DFS. Insert the clone before exploring neighbors or a cycle stack-overflows / duplicates nodes.

Solution

export class Node {
  val: number;
  neighbors: Node[];
  constructor(val = 0, neighbors: Node[] = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}

export function cloneGraph(node: Node | null): Node | null {
  if (!node) return null;
  const clones = new Map<Node, Node>();
  const dfs = (n: Node): Node => {
    const hit = clones.get(n);
    if (hit) return hit;
    const copy = new Node(n.val);
    clones.set(n, copy);
    for (const nb of n.neighbors) copy.neighbors.push(dfs(nb));
    return copy;
  };
  return dfs(node);
}

export class Node {
  val: number;
  neighbors: Node[];
  constructor(val = 0, neighbors: Node[] = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}

export function cloneGraph(node: Node | null): Node | null {
  if (!node) return null;
  const clones = new Map<Node, Node>();
  const dfs = (n: Node): Node => {
    const hit = clones.get(n);
    if (hit) return hit;
    const copy = new Node(n.val);
    clones.set(n, copy);
    for (const nb of n.neighbors) copy.neighbors.push(dfs(nb));
    return copy;
  };
  return dfs(node);
}

BFS with clone map

Unverified

Time O(V+E)Space O(V)

Idea. Clone the start, enqueue it. For each popped node, for each neighbor: clone-on-first-seen and enqueue; always append the cloned neighbor to the cloned node’s list.

Walkthrough. Same cycle: BFS clones 1, then 2 and 4 from 1’s neighbors, then 3; every edge is copied exactly once per direction.

Trade-offs. Same map invariant, explicit queue. Prefer if recursion depth on a long path worries you. Returning the original node (forgetting to clone) still serializes to the same adjacency list — identity checks catch that.

Solution

export class Node {
  val: number;
  neighbors: Node[];
  constructor(val = 0, neighbors: Node[] = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}

export function cloneGraph(node: Node | null): Node | null {
  if (!node) return null;
  const clones = new Map<Node, Node>([[node, new Node(node.val)]]);
  const q: Node[] = [node];
  for (let i = 0; i < q.length; i++) {
    const n = q[i]!;
    for (const nb of n.neighbors) {
      if (!clones.has(nb)) {
        clones.set(nb, new Node(nb.val));
        q.push(nb);
      }
      clones.get(n)!.neighbors.push(clones.get(nb)!);
    }
  }
  return clones.get(node)!;
}

export class Node {
  val: number;
  neighbors: Node[];
  constructor(val = 0, neighbors: Node[] = []) {
    this.val = val;
    this.neighbors = neighbors;
  }
}

export function cloneGraph(node: Node | null): Node | null {
  if (!node) return null;
  const clones = new Map<Node, Node>([[node, new Node(node.val)]]);
  const q: Node[] = [node];
  for (let i = 0; i < q.length; i++) {
    const n = q[i]!;
    for (const nb of n.neighbors) {
      if (!clones.has(nb)) {
        clones.set(nb, new Node(nb.val));
        q.push(nb);
      }
      clones.get(n)!.neighbors.push(clones.get(nb)!);
    }
  }
  return clones.get(node)!;
}

Template connection

Clone-graph shape of Graph DFS: Map<old, new> plus copy-on-visit. The adjacency list is the neighbor enumeration; visited is the clone map.

Reflection

The map sends an original node to its clone. Create the clone and store it before you walk the neighbors, or a back edge clones the same node twice.
DFS and BFS build the same graph. A cycle is visited once because the map already holds the clone. A null start is null.
One node with a self-edge clones that edge. A node with no neighbors has an empty list on the clone.