Deep-copy a whole graph from one node. Walk it with depth-first search, and keep a map from each original to its copy so cycles are cloned once.
▼The problem
LeetCode 133 (Medium). Given a reference to one node of a connected, undirected graph (each node has a val and a list of neighbors), return a deep copy: new nodes with the same values, wired the same way, sharing nothing with the original.
Example (LeetCode's): adjacency [[2,4],[1,3],[2,4],[1,3]], a four-node loop 1-2-3-4-1. A naive recursive copy with no memory goes 1 → 2 → 1 → 2 … forever.
The solution
def cloneGraph(node):
copies = {} # original -> copy
def clone(n):
if n in copies:
return copies[n] # reuse
copy = Node(n.val)
copies[n] = copy # store first
for nb in n.neighbors:
copy.neighbors.append(clone(nb))
return copy
return clone(node) if node else NoneTranscript
Clone Graph. You're given one node of a connected, undirected graph, where each node has a value and a list of neighbors. Return a deep copy: new nodes, wired the same way.
Take four nodes in a loop. One joins two and four, three joins two and four. The copy needs four new nodes and the same four edges, sharing nothing with the original.
The naive way copies a node, then copies each neighbor the same way. But there's a cycle: one copies two, two copies one again, then two again, forever.
The fix is a hash map from each original node to its copy. Before copying a node, check the map. If it's there, reuse that copy. If not, make one and store it right away, before visiting its neighbors.
In code, a helper takes a node. If it's in the map, return its copy. Otherwise, create a node with the same value, store it, then append the clone of each neighbor, and return the copy.
Start at one: new copy, stored. Its neighbor two: new copy. Two sees one, already in the map: reuse it. Then three: new copy, and it sees two: reuse. Then four: new copy, and it sees one and three: both reused. Back at one, four is in the map too. Four copies, every edge rebuilt.
Each node is copied once, each edge is followed from both ends, so the time is big O of V plus E. The map holds V copies: linear space.
Copy once, remember it, reuse it. That's Clone Graph.