Clone Graph — Step-by-Step Visualization

Algorithm Pattern

DFS/BFS with Node Mapping

Key Idea

To perform a deep copy of a graph, we must create new objects for every node. To avoid infinite loops in cyclic graphs and to reuse already cloned nodes, we use a Hash Map to store the mapping from `original_node` to `cloned_node`. If a node is already in the map, we return its clone; otherwise, we create a new node and recursively clone all its neighbors.

Step-by-Step Approach

1. Initialize an empty Hash Map `oldToNew`.
2. Start a DFS (or BFS) from the input node.
3. For each node visited, check if it's already in `oldToNew`.
4. If not, create a copy of the node and add the mapping to the map.
5. Recursively handle all neighbors and add them to the cloned node's neighbor list.

Common Gotchas

• The input format `[[2,4],[1,3],[2,4],[1,3]]` means node 1 is connected to 2 & 4, node 2 to 1 & 3, etc.
• Make sure to handle the case where the input node is null.