Problem Statement
Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a value (int
) and a list (List[Node]
) of its neighbors.
Example 1:
Input:
12
 
43
Expected Output:
12
 
43
Explanation: The graph has four nodes with the following connections:
 Node
1
is connected to nodes2
and4
.  Node
2
is connected to nodes1
and3
.  Node
3
is connected to nodes2
and4
.  Node
4
is connected to nodes1
and3
.
Example 2:
Input:
12
/ \
5 3

4
Expected Output:
12
/ \
5 3

4
Explanation: The graph consists of five nodes with these connections:
 Node
1
is connected to nodes2
and5
.  Node
2
is connected to nodes1
and3
.  Node
3
is connected to nodes2
and4
.  Node
4
is connected to node3
.  Node
5
is connected to node1
.
Example 3:
Input:
12
/ \
4 3
\ /
56
Expected Output:
12
/ \
4 3
\ /
56
Explanation: The graph has six nodes with the following connections:
 Node
1
is connected to nodes2
and4
.  Node
2
is connected to nodes1
and3
.  Node
3
is connected to nodes2
and6
.  Node
4
is connected to nodes1
and5
.  Node
5
is connected to nodes4
and6
.  Node
6
is connected to nodes3
and5
.
Solution
To deep clone a given graph, the primary approach is to traverse the graph using DepthFirst Search (DFS) and simultaneously create clones of the visited nodes. A hashmap (or dictionary) is utilized to track and associate original nodes with their respective clones, ensuring no duplications.

Initialization: Create an empty hashmap to match the original nodes to their clones.

DFS Traversal and Cloning: Traverse the graph with DFS. When encountering a node not in the hashmap, create its clone and map them in the hashmap. Recursively apply DFS for each of the node's neighbors. After cloning a node and all its neighbors, associate the cloned node with the clones of its neighbors.

Termination: Once DFS covers all nodes, return the cloned version of the starting node.
Algorithm Walkthrough (using Example 1):
For the input graph:
12
 
43
 Start with an empty hashmap
visited
.  Begin DFS with node
1
. Node
1
isn't invisited
. Clone it to get1'
and map(1, 1')
in the hashmap.  For each neighbor of node
1
, apply DFS. First with
2
. Node
2
isn't invisited
. Clone to get2'
and map(2, 2')
.  Node
2
's neighbors are1
and3
. Node1
is visited, so link2'
to1'
. Move to3
. Node
3
isn't invisited
. Clone to get3'
and map(3, 3')
.  Node
3
has neighbors2
and4
. Node2
is visited, so link3'
to2'
. Move to4
. Node
4
isn't invisited
. Clone to get4'
and map(4, 4')
.  Node
4
has neighbors1
and3
, both visited. Link4'
to1'
and3'
.
 Node
 Node
 Node
 First with
 Node
 With DFS complete, return the clone of the starting node,
1'
.
Code
Complexity Analysis

Time Complexity: O(N+M) where N is the number of nodes and M is the number of edges. Each node and edge is visited once.

Space Complexity: O(N) as we are creating a clone for each node. Additionally, the recursion stack might use O(H) where H is the depth of the graph (in the worst case this would be O(N)).