Graph Clone

Description

A deep copy of a graph has exactly one new node for each original node, the same connections between them, and no references back into the original. Copying a tree is simple recursion. A graph adds two complications: a node reached along two paths must still be copied only once, and a cycle leads back to a node whose copy isn't finished yet. A map from each original node to its copy solves both.

Copying a tree is easy: copy the node, recursively copy its children. A graph breaks that in two ways. A node can be reached along several paths (shared neighbors), so a naive copy duplicates it; and a cycle leads back to a node that's still being copied, so a naive copy never finishes. A deep copy of a graph has to produce exactly one new node per original node, with the same connections - and never point into the original.

We'll go from simple to more technical:

1. The pattern: a DFS clone that registers each copy before cloning its neighbors.
2. A second flavor: cloning breadth-first with a queue.
3. Where identity maps run in production (deep copies, serialization).
4. What breaks it: registering late, no map, keying by value, and shallow neighbors.

The approach

Node cloneGraph(Node node) {
    if (node == null) return null;
    return clone(node, new HashMap<>());
}

Node clone(Node node, Map<Node, Node> copies) {
    if (copies.containsKey(node)) return copies.get(node);   // already copied (or being copied) - reuse it
    Node copy = new Node(node.val);
    copies.put(node, copy);                                   // register BEFORE visiting neighbors
    for (Node neighbor : node.neighbors) {
        copy.neighbors.add(clone(neighbor, copies));
    }
    return copy;
}

def clone_graph(node: Node | None) -> Node | None:
    if node is None:
        return None
    copies = {}                                  # original node -> its copy

    def clone(n: Node) -> Node:
        if n in copies:
            return copies[n]                     # already copied (or being copied) - reuse it
        copy = Node(n.val)
        copies[n] = copy                         # register BEFORE visiting neighbors
        for neighbor in n.neighbors:
            copy.neighbors.append(clone(neighbor))
        return copy

    return clone(node)

The map from original node to copy does both jobs. A node reached a second time along another path gets its existing copy, so it's never duplicated. And because the copy is registered before its neighbors are cloned, a cycle that leads back to it finds the half-built copy in the map instead of starting another one - which is what makes the recursion stop.

A second flavor: breadth-first cloning

The recursion is as deep as the longest path it follows. A queue does the same job iteratively: create a node's copy the first time it's seen, and wire up edges as each node is processed.

Node cloneGraph(Node start) {
    if (start == null) return null;
    Map<Node, Node> copies = new HashMap<>();
    copies.put(start, new Node(start.val));
    Deque<Node> queue = new ArrayDeque<>(List.of(start));
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        for (Node next : cur.neighbors) {
            if (!copies.containsKey(next)) {          // first sighting: create its copy and schedule it
                copies.put(next, new Node(next.val));
                queue.add(next);
            }
            copies.get(cur).neighbors.add(copies.get(next));
        }
    }
    return copies.get(start);
}

from collections import deque


def clone_graph(start: Node | None) -> Node | None:
    if start is None:
        return None
    copies = {start: Node(start.val)}
    queue = deque([start])
    while queue:
        cur = queue.popleft()
        for nxt in cur.neighbors:
            if nxt not in copies:                # first sighting: create its copy and schedule it
                copies[nxt] = Node(nxt.val)
                queue.append(nxt)
            copies[cur].neighbors.append(copies[nxt])
    return copies[start]

The map is the BFS visited set: a node's copy is created exactly once, at discovery, which is also the moment it's queued. The copy's neighbor lists keep the original order because each node's edges are added while that node is processed.

Where you'll see it

Deep-copying any structure with shared or circular references - an object graph being snapshotted, a document model where nodes point to each other, a workflow definition duplicated for a new tenant - is this "original -> copy" map. Java serialization, Python's copy.deepcopy (its memo dict is keyed by id()) and most deep-clone libraries keep exactly such an identity map to preserve sharing and survive cycles.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. The copy is put into the map only after all its neighbors have been cloned. What happens on a graph where 1 and 2 are neighbors of each other?

2. The graph has no cycles: A->B, A->C, B->D, C->D. Does a clone without any map work?

3. Why key the map by the node rather than by its value?

Key takeaways

• A graph deep copy keeps a map from each original node to its single copy and checks it before creating anything.
• Register the copy before cloning its neighbors - that's what stops the recursion on cycles.
• The map also preserves sharing: a node reached along two paths still gets one copy.
• Key by node identity, not by value - values can repeat.
• DFS recursion or BFS with a queue both work in O(V + E); BFS avoids deep recursion.