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
.
Constraints:
 The number of nodes in the graph is in the range
[0, 100]
. 1 <= Node.val <= 100
Node.val
is unique for each node. There are no repeated edges and no selfloops in the graph.
 The Graph is connected and all nodes can be visited starting from the given node.
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)).