DSA Tracker

Visualize

Clone Graph

DFS with an old-node → new-node map

time O(V + E)space O(V) for the map plus the recursion stack

A cyclic graph breaks the obvious recursion: copying 1 needs 2, copying 2 needs 1, and you loop forever. The fix is to register the new node in a map BEFORE recursing into its neighbours, so the second time the walk arrives at a vertex the map answers instantly with the copy that already exists. That single ordering turns an infinite walk into one visit per vertex, and the map doubles as the visited set.

Details

Animated on: adjacency = {1:[2,4], 2:[1,3], 3:[2,4], 4:[1,3]} — return a deep copy of the graph. Originals are drawn on the left, the copy being built on the right.

Problem:Clone GraphMedium

DFS with an old-node → new-node map

step 1 / 14

Original (left) · Copy (right)

The original has 4 vertices and 4 undirected edges forming the cycle 1-2-3-4-1. A deep copy needs a brand-new vertex for each one, wired the same way, with the originals untouched.

Pseudocode
1FUNCTION clone(node):
2  IF node IN map:
3    RETURN map[node]
4  copy <- NEW NODE(node.val)
5  map[node] <- copy
6  FOR each nb IN node.neighbors:
7    APPEND clone(nb) TO copy.neighbors
8  RETURN copy

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. The original has 4 vertices and 4 undirected edges forming the cycle 1-2-3-4-1. A deep copy needs a brand-new vertex for each one, wired the same way, with the originals untouched.
  2. Start at 1. Make its copy and record map[1] straight away, before looking at any neighbour — a half-built copy in the map is what lets the cycle terminate.
  3. 2 has no copy yet, so build one and put map[2] in place before recursing. 2 frames are open: 1 → 2.
  4. Neighbour 1 is already in the map, so return the existing copy instead of walking into it again, and link 2' to 1'. The copy now holds 1 of the 4 edges.
  5. 3 has no copy yet, so build one and put map[3] in place before recursing. 3 frames are open: 1 → 2 → 3.
  6. Neighbour 2 is already in the map, so return the existing copy instead of walking into it again, and link 3' to 2'. The copy now holds 2 of the 4 edges.
  7. 4 has no copy yet, so build one and put map[4] in place before recursing. 4 frames are open: 1 → 2 → 3 → 4.
  8. Neighbour 1 is already in the map, so return the existing copy instead of walking into it again, and link 4' to 1'. The copy now holds 3 of the 4 edges.
  9. Neighbour 3 is already in the map, so return the existing copy instead of walking into it again, and link 4' to 3'. The copy now holds 4 of the 4 edges.
  10. Every neighbour of 4 is handled, so 4' is finished and the frame returns to 3. 3 frames still open, 1 of 4 vertices fully copied.
  11. Every neighbour of 3 is handled, so 3' is finished and the frame returns to 2. 2 frames still open, 2 of 4 vertices fully copied.
  12. Every neighbour of 2 is handled, so 2' is finished and the frame returns to 1. 1 frame still open, 3 of 4 vertices fully copied.
  13. Neighbour 4 is already copied AND 1'—4' was already linked from the other side, so this pass adds nothing new. Still 4 copied edges — the map keeps the walk finite.
  14. Done: 4 new vertices and 4 new edges. Each vertex was visited once because the map answers the second visit, so the walk is O(V+E) even though the graph is cyclic.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Clone Graph in the editorAll Graph problemsBack to roadmap