Clone Graph
Given a reference to one node of a connected undirected graph, where each node has a value and a list of neighbours, return a deep copy of the entire graph.
- 0 ≤ number of nodes ≤ 100
- Node values are unique 1..n
- No self-loops or repeated edges
- Graph may contain cycles — need to remember what is already cloned
- Map original node → clone
- Traverse every node once
BFS explores in rings of increasing distance, so the first time it reaches a node it has found a shortest path in terms of edge count. "Minimum number of moves" on any state space where each move costs 1 is BFS, whether the states are grid cells, words, or puzzle configurations.
Keep a hash map from original node to its clone. Start with the given node, create its clone, and BFS over the original graph. For each dequeued node, iterate its neighbours: create a clone for any neighbour not yet in the map and enqueue it; then append the neighbour's clone to the current clone's neighbour list. The map both prevents infinite loops on cycles and guarantees one clone per node.
- Recursive DFS with the same map is shorter. Since values are unique, an array indexed by value can replace the hash map.