Clone Graph

Problem

Build systems often need to snapshot in-memory object graphs for undo history or inter-process transfer. Given a reference to a node in a connected undirected graph, return a deep copy of the entire graph. Each node has an integer value and a list of neighbors.

Graph: 1 -- 2
       |    |
       4 -- 3
 
Input: Node(1) with neighbors [2, 4]
Output: New Node(1) with cloned neighbors - no original nodes in result

Try it

Python

Loading editor…

Tests

def build_graph(edges, n):
    nodes = [Node(i) for i in range(1, n + 1)]
    for u, v in edges:
        nodes[u-1].neighbors.append(nodes[v-1])
        nodes[v-1].neighbors.append(nodes[u-1])
    return nodes

def is_deep_copy(original, cloned, visited=None):
    if visited is None:
        visited = set()
    if original is None and cloned is None:
        return True
    if original is cloned:
        return False
    if original.val != cloned.val:
        return False
    visited.add(id(original))
    orig_vals = sorted(n.val for n in original.neighbors)
    clone_vals = sorted(n.val for n in cloned.neighbors)
    return orig_vals == clone_vals

nodes = build_graph([(1,2),(2,3),(3,4),(4,1)], 4)
result = clone_graph(nodes[0])
assert result is not None and result is not nodes[0], "returns new node"
assert is_deep_copy(nodes[0], result), "structure matches"
assert clone_graph(None) is None, "handles None input"
single = Node(1)
cloned_single = clone_graph(single)
assert cloned_single is not single and cloned_single.val==1, "single node"
assert cloned_single.neighbors==[], "single node no neighbors"

Hints (3)

Solution

Approach: DFS with an original-to-clone hash map (visited map that doubles as the clone registry).

The visited dict maps every original node to its freshly minted clone, and it carries two jobs at once - it is the cycle guard and the lookup table that lets shared neighbors point at the same clone object. dfs(original) first checks the map: if original is already there, the clone exists, so return it immediately instead of recursing. Otherwise create the clone, and - this is the critical ordering - register it in the map before touching any neighbor. Only then loop over original.neighbors, recursing into each and appending the returned clones to clone.neighbors. Registering before recursing is what defeats cycles: when a neighbor's recursion eventually loops back to the current node, the map lookup at the top fires and returns the in-progress clone rather than spinning forever. Trace the 4-cycle 1-2-3-4-1: cloning 1 registers clone-1, recurses to 2, 3, 4, and when 4 recurses back to 1 the map already holds clone-1, so the back-edge resolves and the recursion unwinds cleanly.

Edge cases: A None input returns None via the if not node guard. A single isolated node clones to a fresh node with an empty neighbor list - the loop body never runs.

Complexity: O(V + E) time, O(V) space - every node is created once and every edge is walked once; the map plus recursion stack are both O(V).