Clone Graph

You are given a reference to a node in a connected, undirected graph. Each node stores an integer value and a list of its neighbors. Return a deep copy of the entire graph: a new set of nodes with identical values and identical neighbor structure, sharing no objects with the original.

Example#

Given a 4-node square where node 1 connects to 2 and 4, node 2 connects to 1 and 3, node 3 connects to 2 and 4, and node 4 connects to 1 and 3, produce a fresh graph with the same shape. Modifying the copy must not touch the original.

Brute force note#

Copying values alone is easy. The trap is neighbor lists: if you naively create new nodes while walking edges, you loop forever on cycles or create duplicate copies of the same node. You need a way to remember which originals you have already cloned.

Optimal approach#

Keep a hash map from original node to its clone. Traverse the graph (DFS or BFS). When you first see a node, create its clone and store the mapping, then recurse into its neighbors and attach their clones. If a node is already in the map, return the existing clone instead of building a new one. This handles cycles and shared neighbors correctly.

 1class Node:
 2    def __init__(self, val=0, neighbors=None):
 3        self.val = val
 4        self.neighbors = neighbors if neighbors is not None else []
 5
 6
 7def clone_graph(node):
 8    if node is None:
 9        return None
10    clones = {}
11
12    def dfs(original):
13        if original in clones:
14            return clones[original]
15        copy = Node(original.val)
16        clones[original] = copy
17        for nb in original.neighbors:
18            copy.neighbors.append(dfs(nb))
19        return copy
20
21    return dfs(node)
22
23
24a = Node(1)
25b = Node(2)
26a.neighbors = [b]
27b.neighbors = [a]
28cloned = clone_graph(a)
29print(cloned.val, cloned.neighbors[0].val)  # 1 2
30print(cloned is a)  # False

Complexity#

Time is O(V + E): each node and each edge is processed once. Space is O(V) for the clone map plus the recursion stack, which can reach O(V) on a long path.

Traversal choice matters here. Study the DFS and BFS foundations on the graphs topic page, then keep building through the 60-day curriculum.