Clone Graph

Clone Graph is the classic interview test of whether you really understand graph traversal and references. The trick is a single visited map that does double duty: it stops infinite loops and remembers each node's copy.

The slow way first

You might think to copy all the nodes first, then loop again to copy the edges. That works, but it needs two passes and some bookkeeping to match old nodes to new ones. And if you naively recurse into neighbors without remembering anything, you loop forever: A points to B, B points back to A, A points to B... a cycle the recursion never escapes.

The question to ask: how do I copy each node exactly once and still rebuild every edge?

The idea: one visited map, old → new

Do a single DFS. Keep a dictionary visited that maps an original node to its clone. When you reach a node:

1. If it is already in visited, return the copy you made earlier — do not clone it again.
2. Otherwise, make the copy, record it in visited before recursing, then walk its neighbors and attach each neighbor's clone.

Recording the copy before you recurse is what breaks the cycle: when the recursion comes back to a node it has already started, the lookup in step 1 hits and returns instantly.

The visited map is the whole solution: it is both the cycle-guard and the old-to-new translation table.

Walk through it

Step through the animation. The original graph sits on the left; the clone builds up on the right, node by node, as DFS visits. Watch the visited map fill: A, then B, then C, then D. When C reaches back to A, and when D reaches back to A, the node is already in visited — so no new node appears, we just draw the cloned edge using the copy we already made.

Pseudocode

clone(node):
    if node in visited:        # already cloned -> reuse it (breaks cycles)
        return visited[node]
    copy = new Node(node.value)
    visited[node] = copy        # record BEFORE recursing
    for nbr in node.neighbors:
        copy.neighbors.add( clone(nbr) )   # recursion reuses visited
    return copy

The Python solution

def clone_graph(node, visited=None):
    if visited is None:
        visited = {}
    if node in visited:
        return visited[node]
    # make the copy, record it BEFORE recursing
    copy = Node(node.val)
    visited[node] = copy
    for nbr in node.neighbors:
        if nbr not in visited:
            copy.neighbors.append(clone_graph(nbr, visited))
        else:
            copy.neighbors.append(visited[nbr])
    return copy

• visited maps each original node → its clone. It is shared across the whole recursion.
• The early if node in visited return is the cycle-guard: it stops us re-cloning a node we have already started.
• Lines 7-8 are the heart: we create the copy and store it in visited before touching neighbors.
• For each neighbor we either recurse (new node) or grab the already-made copy from visited, then append it to copy.neighbors.

Complexity

We touch every node and every edge exactly once, so the work is O(V + E). The extra space is the visited map plus the recursion stack, both O(V).

When this pattern shows up

Practice