Given a node of a connected undirected graph, return a deep copy of the whole graph. Each node has a value and a list of neighbours.
DSA Animator › DSA Revision › Graph › Clone Graph
Remember: store the copy in the map before visiting neighbours. The map doubles as the visited set. The video solves Clone Graph (LeetCode 133, Medium) with the DFS + Hash Map pattern from the Graph topic, and you can replay every step in the interactive Clone Graph animation.
Given a node of a connected undirected graph, return a deep copy of the whole graph. Each node has a value and a list of neighbours.
For the square 1, 2, 3, 4, where each node connects to the next and 4 connects back to 1, the copy must have the same four nodes and the same four edges.
Copying a node and then naively copying each neighbour runs forever, because the graph has cycles. We need to remember which nodes are already copied.
Use a hash map from each original node to its copy. When you visit a node, first check the map. If the node is already copied, return that copy, which also stops infinite loops. Otherwise create the copy, store it in the map, and then clone every neighbour and attach it.
Visit 1, create its copy, and store it in the map. Its neighbour 2 is new, so create a copy of 2. 2 sees 1 in the map, so it links to the existing copy, and then copies 3. 3 links back to 2 and copies 4. 4 finds both 3 and 1 already in the map, so it only adds links. Every node and edge now exists in the copy.
In code, return null for a null node. If the map contains the node, return the stored copy. Otherwise create a new node with the same value, and put it in the map before recursing. Then, for every neighbour, add the cloned neighbour to the copy list. Each node and edge is processed once, so it's O of n plus e.
Remember: store the copy in the map before visiting neighbours. The map doubles as the visited set.