Clone Graph
Clone Graph is LeetCode 133 (Medium). You are given a reference to one node of a connected, undirected graph. Return a deep copy of the whole graph: new node objects with the same values, wired together exactly like the original.
- Each node has an integer
valand a listneighbors. - Values are unique and run from 1 to the number of nodes, so a value identifies its node.
- The copy must not share a single node with the original.
- The number of nodes in the graph is in the range [0, 100].
- 1 <= Node.val <= 100
- Node.val is unique for each node.
- There are no repeated edges and no self-loops in the graph.
- The Graph is connected and all nodes can be visited starting from the given node.
Intuition
Copying one node is easy; the trouble is the edges. A naive recursive copy loops forever on a cycle, and copies a node twice when two paths reach it, so the result no longer has the same shape.
Both problems disappear with one hash map from original node to its copy. The map answers "have I copied this already?", so each node is copied once and every edge to it points at that single copy. The key detail is order: the copy goes into the map before its neighbours are visited, so when a cycle leads back, there is already a node to point at instead of another recursion.
Any deep copy of a structure with shared or cyclic references (graphs, lists with random pointers) needs a map from old objects to new ones. The traversal (DFS or BFS) just decides the order in which nodes are reached.
Approach
Before reading on, trace a plain recursive copy on the square graph 1-2-3-4-1. Where does it loop? What single piece of information would let it stop?
Two ways to solve it
Copy a node, store it in the map, then clone each neighbour recursively and attach it.
- Short: the map doubles as the visited set.
- Natural: each call finishes one node's neighbour list.
- Limit: depth grows with the longest path.
The usual interview answer.
Queue the start node; for each node popped, copy unseen neighbours, queue them and link the copies.
- No recursion: safe on very deep graphs.
- Same cost: each node and edge handled once.
- Watch out: copy a neighbour when it is queued, not when popped.
Pick it when depth could be a problem.
Both visit every node and edge once, so the cost is the same; DFS wins on simplicity. The steps, code and live demo below follow DFS; the BFS code comes after the demo.
Handle the empty graph
If node is None, return None straight away. An empty graph is a valid input, and checking it first means the rest of the code can assume a real start node with a value and a neighbour list.
Keep a map of copies
Create copies, a map from each original node to its clone. It does two jobs at once: it is the visited set that stops cycles, and it is the lookup that makes every edge point at one shared copy instead of a fresh duplicate.
Copy with DFS
clone(n):
- if
nis incopies, returncopies[n]; - create
copy = Node(n.val)and storecopies[n] = copy; - for each neighbour, append
clone(neighbour)tocopy.neighbors; - return
copy.
Recursion depth can reach the node count, so for very large graphs the same logic runs with an explicit stack or a BFS queue.
Return the copy of the start node
Return clone(node), the copy of the start node, and the clone graph solution is done. The graph is connected, so every node is reachable from the start and is copied exactly once, which gives O(V + E) time and O(V) space for the map.
Clone Graph solution in Python | C++ | Java
node.val.BFS version (queue)
The same copy map with a queue instead of recursion. Create a neighbour's copy the moment it is first seen, before queueing it, so each node is copied once; then wire each popped node's copy to its neighbours' copies.
Common pitfalls
Storing the copy after visiting the neighbours
copy = Node(n.val)
for nb in n.neighbors:
copy.neighbors.append(clone(nb))
copies[n] = copycopy = Node(n.val)
copies[n] = copy
for nb in n.neighbors:
copy.neighbors.append(clone(nb))A cycle leads back to n before it is in the map, so n is copied again, and again: infinite recursion. The map entry must exist before any neighbour is visited.
Keeping a visited set of original nodes only
if n in visited:
return nif n in copies:
return copies[n]Returning the original node wires the copy back into the old graph, so the result is not a deep copy. You need the copy, which is why the map stores old -> new.
Edge cases
node is None: return None before touching the map.
Input [[]]. One copy is made with an empty neighbors list; the loop over neighbours does nothing.
Complexity
Clone Graph FAQ
What does clone graph mean?
Build a new graph with the same values and the same connections, where every node is a new object. No node or neighbour list in the copy may point into the original graph.
How do you clone a graph with DFS?
- Problem: deep copy a connected undirected graph given one node.
- Data structure: hash map
copiesfrom original node to copy. - DFS: if a node is in the map, return its copy; otherwise create the copy, store it, then recursively clone each neighbour and append it.
- Why store first: a cycle leading back finds the copy and stops.
- Complexity: O(V + E) time, O(V) space.
- Example: the square 1-2-3-4-1 produces 4 new nodes and 8 neighbour entries.
Why do we need a hash map in clone graph?
The graph can have cycles and shared neighbours. The map records which nodes already have a copy, so the traversal stops at them and every edge points at the single copy of its node.