Clone Graph

133.Clone Graph

Graph

Depth-First Search

Hash Table

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 of its neighbors.

Example:

Input:

adjList = [[2,4],[1,3],[2,4],[1,3]]

→

Output:

[[2,4],[1,3],[2,4],[1,3]]

Return new graph with same structure but different node references

Algorithm:

1. Use HashMap to store original to clone node mapping
2. DFS through original graph
3. Create new nodes as needed
4. Clone neighbor relationships recursively

Complexity:

Time: O(V + E) | Space: O(V) where V is vertices, E is edges

Java Solution:

public Node cloneGraph(Node node) {
    return clone(node, new HashMap<>());
}

private Node clone(Node node, Map<Node, Node> map) {
    // Handle null case
    if (node == null) return null;
    
    // Return existing clone if already processed
    if (map.containsKey(node)) return map.get(node);

    // Create new node
    Node curr = new Node(node.val);
    map.put(node, curr);

    // Clone all neighbors recursively
    for (Node neighbor : node.neighbors)
        curr.neighbors.add(clone(neighbor, map));
    
    return curr;
}

Python Solution:

def cloneGraph(self, node: Node) -> Node:
    def clone(node: Node, visited: dict) -> Node:
        # Handle null case
        if not node: 
            return None
            
        # Return existing clone if already processed
        if node in visited:
            return visited[node]
        
        # Create new node and clone neighbors
        copy = Node(node.val)
        visited[node] = copy
        
        for neighbor in node.neighbors:
            copy.neighbors.append(clone(neighbor, visited))
            
        return copy
    
    return clone(node, {})

C++ Solution:

Node* cloneGraph(Node* node) {
    return clone(node, unordered_map<Node*, Node*>());
}

Node* clone(Node* node, unordered_map<Node*, Node*>& map) {
    // Handle null case
    if (!node) return nullptr;
    
    // Return existing clone if already processed
    if (map.count(node)) return map[node];
    
    // Create new node
    Node* copy = new Node(node->val);
    map[node] = copy;
    
    // Clone all neighbors recursively
    for (Node* neighbor : node->neighbors) {
        copy->neighbors.push_back(clone(neighbor, map));
    }
    
    return copy;
}