Clone Graph
Deep copy a connected undirected graph.
Examples
Return a deep copy of the graph.
Problem Understanding
You are handed one node of a connected, undirected graph.
Build and return a deep copy of the whole graph.
Deep Copy: New nodes, new edges. You cannot return references to the original nodes.
Algorithm Strategy
We need to traverse the entire graph and create a copy of each node exactly once.
Key Tool: HashMap<OldNode, NewNode>.
- Check Map: If we already cloned this node, return the
NewNodefrom the map (handles cycles). - Create: If not, create
NewNode(val)and add to map. - Recurse: Iterate through
OldNode.neighbors. For each neighbor, recursively callclone(neighbor)and add the result toNewNode.neighbors.
Visualization
The original graph is on the left and the copy grows on the right. A copy appears the moment clone creates it and goes into the map straight away. A copy edge is first an arrow — one node’s neighbour list updated — and becomes a plain line when the other end links back. Each call that finds its node already in the map is a map hit: the recursion stops there instead of going round the cycle again.
Dry Run
Input: adjList = [[2,4],[1,3],[2,4],[1,3]] — a square, 1-2-3-4-1.
| Step | Call | Map | What happens |
|---|---|---|---|
| 1 | clone(1) |
{1} |
No copy yet: create copy 1 and store it. First neighbour: 2. |
| 2 | clone(2) |
{1, 2} |
Create and store copy 2. First neighbour: 1. |
| 3 | clone(1) |
{1, 2} |
1 is in the map: return copy 1 at once. Copy 2 links to copy 1. |
| 4 | clone(3) |
{1, 2, 3} |
2’s next neighbour. Create and store copy 3. Its neighbour 2 is in the map: link 3 → 2. |
| 5 | clone(4) |
{1, 2, 3, 4} |
Create and store copy 4. Neighbours 1 and 3 are both in the map: link 4 → 1 and 4 → 3. Return copy 4. |
| 6 | back in clone(3) |
— | Link 3 → 4. Return copy 3. |
| 7 | back in clone(2) |
— | Link 2 → 3. Return copy 2. |
| 8 | back in clone(1) |
— | Link 1 → 2. Its next neighbour, 4, is in the map: link 1 → 4. Return copy 1. |
Edge Cases & Common Mistakes
Be careful with these scenarios:
Empty Graph: Input
nodeisnull. Returnnullimmediately.Single Node: A graph with just one node and no neighbors.
Cycles: The graph can contain cycles (e.g., A -> B -> A). Infinite recursion happens if you don't use the map to check visited nodes.
Reference Identity: You must return a new node instance, not the original reference.
Undirected Edge Duplication: In an undirected graph, A-B is one edge, but in adjacency lists, it appears as B in A's neighbors AND A in B's neighbors. Ensure you don't process it infinitely (handled by map).
Solution (DFS)
One map from each original node to its copy. clone checks the map before anything else, and stores a new copy before visiting its neighbours, so a cycle leads back to a copy instead of into endless recursion. The C version uses an array indexed by value as the map: LeetCode guarantees unique values from 1 to 100.
Clone Graph Code
1var cloneGraph = function(node) {2 if (!node) return null;3 const copies = new Map();45 function clone(original) {6 if (copies.has(original)) {7 return copies.get(original);8 }9 const copy = new _Node(original.val);10 copies.set(original, copy);11 for (const neighbor of original.neighbors) {12 copy.neighbors.push(clone(neighbor));13 }14 return copy;15 }1617 return clone(node);18};