Clone Graph

Create a deep copy of an undirected graph represented with adjacency lists

Language Selection

Choose your preferred programming language

Showing: Python

Clone Graph

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.

Input/Output Specifications

Input: A reference to a node in a connected undirected graph
Output: A reference to the cloned graph’s corresponding node
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 self-loops in the graph
- The graph is connected and all nodes are reachable from the given node

Node Definition

class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

Examples

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: 
Graph has 4 nodes:
- Node 1 with neighbors [2, 4]
- Node 2 with neighbors [1, 3] 
- Node 3 with neighbors [2, 4]
- Node 4 with neighbors [1, 3]

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Single node with no neighbors

Example 3:

Input: adjList = []
Output: []
Explanation: Empty graph (null input)

Solution Approaches

Approach 1: DFS with HashMap (Optimal)

Use depth-first search with a hashmap to track visited nodes and avoid infinite recursion.

Algorithm Explanation

Base Case: If input node is null, return null
HashMap: Use a map to store original node → cloned node mapping
DFS Traversal: For each node:
- If already cloned, return the cloned version
- Create new node with same value
- Store in map to avoid re-processing
- Recursively clone all neighbors
Return: The cloned version of the input node

Implementation

Python:

class Solution:
    """
    DFS approach with HashMap for graph cloning
    Time: O(V + E) where V is vertices, E is edges
    Space: O(V) for the hashmap and recursion stack
    """
    
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        
        # HashMap to store original -> cloned node mapping
        cloned = {}
        
        def dfs(node):
            # If already cloned, return the clone
            if node in cloned:
                return cloned[node]
            
            # Create clone of current node
            clone = Node(node.val)
            cloned[node] = clone
            
            # Clone all neighbors recursively
            for neighbor in node.neighbors:
                clone.neighbors.append(dfs(neighbor))
            
            return clone
        
        return dfs(node)

Java:

class Solution {
    /**
     * DFS approach with HashMap for graph cloning
     * Time: O(V + E) where V is vertices, E is edges
     * Space: O(V) for the hashmap and recursion stack
     */
    
    private Map<Node, Node> cloned = new HashMap<>();
    
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        
        return dfs(node);
    }
    
    private Node dfs(Node node) {
        // If already cloned, return the clone
        if (cloned.containsKey(node)) {
            return cloned.get(node);
        }
        
        // Create clone of current node
        Node clone = new Node(node.val);
        cloned.put(node, clone);
        
        // Clone all neighbors recursively
        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(dfs(neighbor));
        }
        
        return clone;
    }
}

Go:

// cloneGraph - DFS approach with map for graph cloning
// Time: O(V + E) where V is vertices, E is edges
// Space: O(V) for the map and recursion stack
func cloneGraph(node *Node) *Node {
    if node == nil {
        return nil
    }
    
    cloned := make(map[*Node]*Node)
    
    var dfs func(*Node) *Node
    dfs = func(node *Node) *Node {
        // If already cloned, return the clone
        if clone, exists := cloned[node]; exists {
            return clone
        }
        
        // Create clone of current node
        clone := &Node{Val: node.Val, Neighbors: []*Node{}}
        cloned[node] = clone
        
        // Clone all neighbors recursively
        for _, neighbor := range node.Neighbors {
            clone.Neighbors = append(clone.Neighbors, dfs(neighbor))
        }
        
        return clone
    }
    
    return dfs(node)
}

JavaScript:

/**
 * DFS approach with Map for graph cloning
 * Time: O(V + E) where V is vertices, E is edges
 * Space: O(V) for the map and recursion stack
 */
function cloneGraph(node) {
    if (!node) return null;
    
    // Map to store original -> cloned node mapping
    const cloned = new Map();
    
    function dfs(node) {
        // If already cloned, return the clone
        if (cloned.has(node)) {
            return cloned.get(node);
        }
        
        // Create clone of current node
        const clone = new Node(node.val);
        cloned.set(node, clone);
        
        // Clone all neighbors recursively
        for (const neighbor of node.neighbors) {
            clone.neighbors.push(dfs(neighbor));
        }
        
        return clone;
    }
    
    return dfs(node);
}

C#:

public class Solution {
    /// <summary>
    /// DFS approach with Dictionary for graph cloning
    /// Time: O(V + E) where V is vertices, E is edges
    /// Space: O(V) for the dictionary and recursion stack
    /// </summary>
    
    private Dictionary<Node, Node> cloned = new Dictionary<Node, Node>();
    
    public Node CloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        
        return Dfs(node);
    }
    
    private Node Dfs(Node node) {
        // If already cloned, return the clone
        if (cloned.ContainsKey(node)) {
            return cloned[node];
        }
        
        // Create clone of current node
        Node clone = new Node(node.val);
        cloned[node] = clone;
        
        // Clone all neighbors recursively
        foreach (Node neighbor in node.neighbors) {
            clone.neighbors.Add(Dfs(neighbor));
        }
        
        return clone;
    }
}

Approach 2: BFS with HashMap

Use breadth-first search with a queue for iterative graph cloning.

Algorithm Explanation

Initialize: Create queue with starting node and hashmap for clones
BFS Loop: While queue is not empty:
- Dequeue current node
- For each neighbor of current node:
  - If neighbor not cloned, create clone and add to queue
  - Add neighbor clone to current node’s neighbor list
Return: The cloned version of the input node

Implementation

Python:

from collections import deque

class Solution:
    """
    BFS approach with HashMap for graph cloning
    Time: O(V + E) where V is vertices, E is edges
    Space: O(V) for the hashmap and queue
    """
    
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        
        # HashMap to store original -> cloned node mapping
        cloned = {node: Node(node.val)}
        queue = deque([node])
        
        while queue:
            current = queue.popleft()
            
            for neighbor in current.neighbors:
                if neighbor not in cloned:
                    # Create clone and add to queue for processing
                    cloned[neighbor] = Node(neighbor.val)
                    queue.append(neighbor)
                
                # Add cloned neighbor to current node's clone
                cloned[current].neighbors.append(cloned[neighbor])
        
        return cloned[node]

Java:

class Solution {
    /**
     * BFS approach with HashMap for graph cloning
     * Time: O(V + E) where V is vertices, E is edges
     * Space: O(V) for the hashmap and queue
     */
    
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        
        Map<Node, Node> cloned = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        
        // Initialize with starting node
        cloned.put(node, new Node(node.val));
        queue.offer(node);
        
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            
            for (Node neighbor : current.neighbors) {
                if (!cloned.containsKey(neighbor)) {
                    // Create clone and add to queue for processing
                    cloned.put(neighbor, new Node(neighbor.val));
                    queue.offer(neighbor);
                }
                
                // Add cloned neighbor to current node's clone
                cloned.get(current).neighbors.add(cloned.get(neighbor));
            }
        }
        
        return cloned.get(node);
    }
}

Complexity Analysis

DFS Approach

Time Complexity: O(V + E) where V is number of vertices and E is number of edges
Space Complexity: O(V) for the hashmap and O(V) for recursion stack = O(V)

BFS Approach

Time Complexity: O(V + E) where V is number of vertices and E is number of edges
Space Complexity: O(V) for the hashmap and O(V) for the queue = O(V)

Key Insights

Deep Copy Requirement: Must create entirely new nodes, not just copy references
Cycle Handling: HashMap prevents infinite loops in cyclic graphs
Complete Cloning: All nodes and edges must be preserved in the clone
Memory Efficiency: Each original node maps to exactly one cloned node

Edge Cases

Null Input: Empty graph should return null
Single Node: Node with no neighbors
Two Node Cycle: Nodes pointing to each other
Linear Chain: Nodes connected in a line
Complete Graph: Every node connected to every other node
Self-loops: Node pointing to itself (though problem states no self-loops)

Test Cases

# Test cases for validation
def test_clone_graph():
    # Test case 1: Single node
    node1 = Node(1)
    cloned1 = cloneGraph(node1)
    assert cloned1.val == 1
    assert len(cloned1.neighbors) == 0
    assert cloned1 is not node1  # Different objects
    
    # Test case 2: Two connected nodes
    node1 = Node(1)
    node2 = Node(2)
    node1.neighbors = [node2]
    node2.neighbors = [node1]
    
    cloned1 = cloneGraph(node1)
    assert cloned1.val == 1
    assert cloned1.neighbors[0].val == 2
    assert cloned1.neighbors[0].neighbors[0] is cloned1  # Cycle preserved
    
    # Test case 3: Null input
    assert cloneGraph(None) is None

Follow-up Questions

Clone Directed Graph: How would the approach change for directed graphs?
Clone with Weights: How to clone graphs with weighted edges?
Selective Cloning: Clone only nodes that satisfy certain conditions
Memory Optimization: Can we reduce space complexity for specific graph types?

Common Mistakes

Forgetting HashMap: Leading to infinite recursion in cycles
Shallow Copy: Copying references instead of creating new nodes
Incomplete Cloning: Missing edges or nodes in the final graph
Reference Confusion: Mixing original and cloned node references

Interview Tips

Clarify Requirements: Ask about graph properties (directed/undirected, cycles, etc.)
Draw Example: Visualize the graph structure and cloning process
Explain Approach: Describe why hashmap is necessary for cycle detection
Handle Edge Cases: Always consider null input and single node cases
Code Incrementally: Start with structure, then add logic step by step
Verify Cloning: Ensure the clone is completely independent of the original