Clone Graph

LeetCode 133: Clone Graph Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes Depth-First Search (DFS) combined with a Hash Map to create a deep copy of each node exactly once, using the map to handle cycles and prevent infinite recursion.

The Clone Graph problem asks us to create a deep copy of a connected undirected graph. We are given a reference to a single node in the graph. A "deep copy" means we must create entirely new instances for every node and reconstruct the exact same edge structure (neighbor connections) as the original graph. The new graph must not contain any references to nodes from the original graph.

This is a classic graph problem, often referred to as LeetCode 133, and serves as a fundamental test of graph traversal and object referencing skills.

Brute Force Approach for Clone Graph

A naive approach might attempt to traverse the graph using recursion, creating a new copy of the current node and then immediately recursively calling the function for all its neighbors.

1# Pseudo-code for Naive Approach
2def clone(node):
3    if not node: return None
4    newNode = Node(node.val)
5    for neighbor in node.neighbors:
6        newNode.neighbors.append(clone(neighbor)) # Recursive call
7    return newNode

Why this fails

This approach fails critically because undirected graphs often contain cycles (e.g., A connects to B, and B connects back to A).

1. Infinite Recursion: When clone(A) calls clone(B), clone(B) will see A as a neighbor and call clone(A) again. This creates an infinite loop, resulting in a Stack Overflow Error (Time Limit Exceeded or Runtime Error).
2. Duplicate Nodes: Even without infinite loops (e.g., a Diamond graph), a naive traversal without state tracking would create multiple distinct copies of the same original node every time it is reached via a different path. This violates the requirement of a graph isomorphism.

Algorithm Strategy: Graph Traversal Patterns (DFS & BFS)

We can implement this using Depth-First Search (DFS). The strategy relies on a recursive function and a global (or passed-down) hash map.

1. State Management: Maintain a Hash Map visited where the key is the reference to an original node and the value is the reference to the corresponding cloned node.
2. Base Case (Null): If the input node is null, return null.
3. Base Case (Visited): If the input node is already in visited, return the stored clone immediately. This handles cycles and shared neighbors.
4. Recursive Step (Clone & Traverse):
   • Create a new node with the same value as the input node.
   • Crucial Step: Add this new node to the visited map before iterating through neighbors. This anchors the node so that recursive calls can find it.
   • Iterate through the neighbors of the original node.
   • For each neighbor, recursively call the function and append the result to the new node's neighbor list.
5. Return: Return the newly created clone.

Execution Flow

Let's trace the algorithm on a simple graph: 1 -- 2.

1. Call cloneGraph(Node 1):

   • Map is empty.
   • Create Clone 1.
   • Update Map: {Node 1: Clone 1}.
   • Iterate neighbors of Node 1: [Node 2].

2. Recursive Call cloneGraph(Node 2):

   • Node 2 is not in Map.
   • Create Clone 2.
   • Update Map: {Node 1: Clone 1, Node 2: Clone 2}.
   • Iterate neighbors of Node 2: [Node 1].

3. Recursive Call cloneGraph(Node 1) (from inside Node 2's context):

   • Node 1 is in Map.
   • Return Clone 1.

4. Back in cloneGraph(Node 2):

   • Add Clone 1 to Clone 2.neighbors.
   • End of neighbors.
   • Return Clone 2.

5. Back in cloneGraph(Node 1):

   • Add Clone 2 to Clone 1.neighbors.
   • End of neighbors.
   • Return Clone 1.

The result is a new graph structure Clone 1 -- Clone 2 that mirrors the original.

Proof of Correctness

The correctness relies on the invariant enforced by the Hash Map: Every node in the original connected component is instantiated exactly once.

1. Termination: Since the number of nodes $N$ is finite and we record every visited node in the map immediately, the DFS will never process the same node twice as a "new" node. This guarantees the recursion terminates.
2. Connectivity: The algorithm iterates over every neighbor of every visited node. Therefore, if edge $(u, v)$ exists in the original graph, the edge $(clone(u), clone(v))$ will be created in the cloned graph.
3. Deep Copy: We explicitly create new Node(val) for every unique key in the map, ensuring no references to the original graph persist in the returned structure.

Pattern Reuse Notes

The Graph - Deep Copy / Cloning pattern and the use of a Hash Map during traversal are applicable to several other problems:

• LeetCode 1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance - While primarily shortest path, managing graph state and neighbors is similar.
• LeetCode 138: Copy List with Random Pointer - This is the Linked List equivalent of Clone Graph. It requires a map to handle the random pointers which act like arbitrary graph edges.
• LeetCode 1490: Clone N-ary Tree - A simplified version of Clone Graph where there are no cycles, but the deep copy logic remains identical.

Reference Implementation

C++ Solution for LeetCode 133

1/*
2// Definition for a Node.
3class Node {
4public:
5    int val;
6    vector<Node*> neighbors;
7    Node() {
8        val = 0;
9        neighbors = vector<Node*>();
10    }
11    Node(int _val) {
12        val = _val;
13        neighbors = vector<Node*>();
14    }
15    Node(int _val, vector<Node*> _neighbors) {
16        val = _val;
17        neighbors = _neighbors;
18    }
19};
20*/
21
22class Solution {
23private:
24    // Map to store mapping from original node to cloned node
25    unordered_map<Node*, Node*> visited;
26
27public:
28    Node* cloneGraph(Node* node) {
29        if (node == nullptr) {
30            return nullptr;
31        }
32
33        // If the node is already visited, return the cloned instance
34        if (visited.find(node) != visited.end()) {
35            return visited[node];
36        }
37
38        // Create the clone for the current node
39        Node* clone = new Node(node->val);
40        
41        // Add to map immediately to handle cycles
42        visited[node] = clone;
43
44        // Iterate through neighbors and clone them recursively
45        for (Node* neighbor : node->neighbors) {
46            clone->neighbors.push_back(cloneGraph(neighbor));
47        }
48
49        return clone;
50    }
51};

Java Solution for LeetCode 133

1/*
2// Definition for a Node.
3class Node {
4    public int val;
5    public List<Node> neighbors;
6    public Node() {
7        val = 0;
8        neighbors = new ArrayList<Node>();
9    }
10    public Node(int _val) {
11        val = _val;
12        neighbors = new ArrayList<Node>();
13    }
14    public Node(int _val, ArrayList<Node> _neighbors) {
15        val = _val;
16        neighbors = _neighbors;
17    }
18}
19*/
20
21class Solution {
22    // HashMap to keep track of visited nodes and their clones
23    private HashMap<Node, Node> visited = new HashMap<>();
24
25    public Node cloneGraph(Node node) {
26        if (node == null) {
27            return null;
28        }
29
30        // If the node was already cloned, return the reference
31        if (visited.containsKey(node)) {
32            return visited.get(node);
33        }
34
35        // Create a new node (clone)
36        Node clone = new Node(node.val);
37        
38        // Store the clone in the map immediately
39        visited.put(node, clone);
40
41        // Recursively clone neighbors
42        for (Node neighbor : node.neighbors) {
43            clone.neighbors.add(cloneGraph(neighbor));
44        }
45
46        return clone;
47    }
48}

Python Solution for LeetCode 133

1"""
2# Definition for a Node.
3class Node:
4    def __init__(self, val = 0, neighbors = None):
5        self.val = val
6        self.neighbors = neighbors if neighbors is not None else []
7"""
8
9class Solution:
10    def __init__(self):
11        # Dictionary to save the visited nodes. 
12        # Key: Original Node, Value: Cloned Node
13        self.visited = {}
14
15    def cloneGraph(self, node: 'Node') -> 'Node':
16        if not node:
17            return None
18
19        # If the node is already visited, return the clone from the dictionary
20        if node in self.visited:
21            return self.visited[node]
22
23        # Create a new node with the value of the original node
24        clone_node = Node(node.val, [])
25        
26        # Add to visited dictionary immediately to prevent cycles
27        self.visited[node] = clone_node
28
29        # Iterate through the neighbors to generate their clones
30        if node.neighbors:
31            for neighbor in node.neighbors:
32                clone_node.neighbors.append(self.cloneGraph(neighbor))
33
34        return clone_node