{—}
visited/cloneMap
Deep-copy an undirected graph by running a BFS/DFS from the entry node, using a single Map<original, clone> that simultaneously prevents infinite loops and acts as the clone registry — so every node is created exactly once and every edge is wired exactly once.
Given a reference to any node in a connected undirected graph, return a deep copy of the entire graph — new node objects, same structure. The example graph is a 4-node cycle: 1 — 2 — 3 — 4 — 1. Each node also connects to its "opposite" (1–3, 2–4). Cloning means four new Node objects whose neighbors arrays mirror the original topology. The catch: cycles mean naively following neighbors loops forever.
Map<original, clone>. Before visiting a neighbor, check the map: if the neighbor is already a key, it has been cloned — reuse that clone. This check does two things at once: it prevents re-enqueueing visited nodes (cycle safety), and it hands back the correct clone object to wire into the current node's neighbor list. You never need a separate visited set.null, return null.cloneMap, and enqueue the original start node.cur. Retrieve its clone from the map.neighbor of cur: if it's not in the map yet, create its clone, enqueue the original, and add it to the map. Either way, push cloneMap.get(neighbor)! into cur's clone.neighbors.cloneMap.get(startNode)! is the root of the new graph.visited set alongside the map — it's redundant. Membership in the map IS the visited check. If cloneMap.has(neighbor)is true, you've already created its clone and enqueued it; no need for a second data structure.DFS with the same map works identically — replace the queue with a stack (or use recursion). Recursive DFS is the most compact form: if (cloneMap.has(node)) return cloneMap.get(node)!; at the top of the function, then clone, recurse on neighbors, return.
4 nodes. Start BFS from node 1. We use a Map<original, clone> that does double duty: prevents revisiting AND returns the existing clone.class _Node {
val: number;
neighbors: _Node[];
constructor(val = 0, neighbors: _Node[] = []) {
this.val = val;
this.neighbors = neighbors;
}
}
function cloneGraph(node: _Node | null): _Node | null {
if (!node) return null;
// Map from original node → its deep clone.
// It serves two roles at once: visited set AND clone registry.
const cloneMap = new Map<_Node, _Node>();
const queue: _Node[] = [node];
cloneMap.set(node, new _Node(node.val));
while (queue.length > 0) {
const cur = queue.shift()!;
const curClone = cloneMap.get(cur)!;
for (const neighbor of cur.neighbors) {
if (!cloneMap.has(neighbor)) {
// First visit: create the clone and enqueue the original.
cloneMap.set(neighbor, new _Node(neighbor.val));
queue.push(neighbor);
}
// Whether brand-new or already seen, wire the edge.
curClone.neighbors.push(cloneMap.get(neighbor)!);
}
}
return cloneMap.get(node)!;
}nullearly also means we never have to handle the "start node missing from map" edge case below.node before the loop so the map is never empty when we enter the BFS. The original node is enqueued so its neighbors get wired in the first iteration.queue.shift() gives us an original node. cloneMap.get(cur)! is safe because we only enqueue a node the moment we add it to the map — so a dequeued node is always in the map.curClone.neighbors. Moving this line outside the if block is the key simplification — no duplicated push.cloneMap.get(node)! is the entry point of the new graph.if (map.has(n)) return map.get(n)!; as the base case, then clone, recurse each neighbor, return.Map<OldNode, NewNode> handles both the next-pointer and the random-pointer wiring in two passes (or one DFS pass).node.val as the key.| deep-copy a graph or linked structure with back-references | Map<original, clone> |
| BFS/DFS on a graph that may have cycles | cloneMap doubles as visited set |
| Copy List with Random Pointer | same node→copy map trick |
| need to return an existing copy, not create a duplicate | map.has() guard before new Node() |
function cloneGraph(node: _Node | null): _Node | null {
if (!node) return null;
const cloneMap = new Map<_Node, _Node>();
const queue: _Node[] = [node];
cloneMap.set(node, new _Node(node.val));
while (queue.length > 0) {
const cur = queue.shift()!;
for (const nb of cur.neighbors) {
if (!cloneMap.has(nb)) {
cloneMap.set(nb, new _Node(nb.val));
queue.push(nb);
}
cloneMap.get(cur)!.neighbors.push(cloneMap.get(nb)!);
}
}
return cloneMap.get(node)!;
}cloneMap.has(neighbor)is true iff we've already cloned it — no separate visited set needed.2 and find its neighbor 4 already in cloneMap. What should you do?1: 2,4; 2: 1,3; 3: 2,4; 4: 1,3. After fully processing node 1 (dequeued first), which nodes are in the clone map?