Pattern visualizer

Clone Graph

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. 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..

DFS with an old-node → new-node map

time O(V + E)space O(V) for the map plus the recursion stackstep 1 / 14

Original (left) · Copy (right)

line 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.

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

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap