Clone Graph
Map original nodes to their clones as you traverse.
The Clone Map, Step by Step
Problem
Given a reference to a node in a connected undirected graph, return a completely independent copy of the entire graph. Each copied node must preserve the value and neighbor relationships of its original, including cycles. Return an empty result when the input reference is absent.
Examples
Input: Adjacency list: 1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]; start = 1
Output: A cloned graph with adjacency list 1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]
Input: Adjacency list: 1: []; start = 1
Output: A cloned node 1 with no neighbors
The Goal
Copy a connected, undirected graph. Return the copy of the start node, where every node is new and every neighbor list matches the original's.
For the four-node cycle 1–2–3–4–1, the copy is a new cycle, 1′–2′–3′–4′–1′, that shares no node with the original.
The hard part: a node can be reached by several paths, and a cycle leads back to where you started.
Same shape, new nodes
Every node in the copy is new, and its neighbor list points at other new nodes, in the same order as the original's.
One copy per node, never two.
Key Idea: Map Each Node to Its Clone
Keep a map from each original node to its clone. Make a node's clone the moment you first see it, before you queue the node.
A second path to the same node then finds the clone in the map and reuses it. A cycle that leads back to node 1 finds 1′ there, instead of making another copy or going around forever.
A node's clone is made and stored the first time the node is seen.
2′ is made while node 1 is being copied.
Breadth-First Copy
Popping a node copies its neighbor list, one entry at a time.
from collections import deque
def clone_graph(node):
if node is None:
return None
clones = {node: Node(node.val)}
queue = deque([node])
while queue:
current = queue.popleft()
for neighbor in current.neighbors:
if neighbor not in clones:
clones[neighbor] = Node(neighbor.val)
queue.append(neighbor)
clones[current].neighbors.append(clones[neighbor])
return clones[node]A depth-first copy uses the same map, with recursion in place of the queue.
| Approach | Worklist | Strength |
|---|---|---|
| BFS | Queue | No recursion limit to hit |
| DFS | Call stack | Shortest code |
Walkthrough
Run it on the cycle [[2,4],[1,3],[2,4],[1,3]].
Node 1 is popped first. Its neighbors 2 and 4 are new, so 2′ and 4′ are made and queued, and 1′ lists both.
Node 2 lists 1 and 3. Node 1 already has 1′, so the map hands it back. Node 3 is new: make 3′ and queue 3.
Nodes 4 and 3 find every neighbor in the map. That's four clones and eight list entries, and the copy's cycle closes.
Checkpoint · predict the next step
Step 5 of 20 on the stage: Append 2′ to the neighbor list of 1′.
current on 1 · neighbor on 2 · queue = [2] · visit order = [] · clones: 1′, 2′ · clones 2
Pitfalls
- Store a clone in the map before you queue or recurse into its node. Store it later, and a cycle makes a second copy or never ends.
- Link clones to clones. Appending the original neighbor ties the copy back to the old graph.
- An empty graph returns
None. - A single node with no neighbors copies to one node with none.
When should a new node's clone go into the map?
Complexity
Each node gets one clone and is queued once. Popping it reads its neighbor list once, so each edge is read twice, once from each end. Time is O(V + E).
The map holds V clones and the queue at most V nodes, so the extra space is O(V), on top of the copy itself.
One pass over nodes and edges
- Clone each nodeOne map entry each.O(V)
- Copy each neighbor listEach edge, once from each end.O(E)
- Map and queueAt most one entry per node.O(V)
Every node and edge has to be copied, so this is as fast as it gets.
In short
DFS or BFS from the start node, keeping a hash map from each original node to its copy. When you first see a node, create its clone; then wire each clone's neighbors by looking them up (creating them on demand). The map both memoizes and prevents infinite loops on cycles.
Common mistake
Creating duplicate clones for the same node because you didn't check/populate the map before recursing.