Clone Graph: Multiple Solutions and Complexity Analysis

What Is Clone Graph?

Cloning a graph means creating an independent deep copy of an entire graph structure. Each node in the original graph is duplicated, and all edges (neighbor relationships) are recreated in the new graph. The most common version of this problem is LeetCode 133 "Clone Graph", where each node is defined by an integer value and a list of references to its neighbors. The graph can be undirected, may contain cycles, and can be disconnected. The goal is to return a deep copy of the given starting node, such that modifying the clone does not affect the original.

Why It Matters

Graph cloning is a fundamental operation in many real-world scenarios:

Serialization / Deserialization – Saving and loading graph structures in memory.
Immutable Data Structures – Creating safe copies for concurrent access or undo systems.
Distributed Systems – Replicating network topologies or dependency graphs.
Algorithm Prototyping – Testing graph algorithms without mutating the original dataset.
Graph Databases – Snapshotting or branching a graph state.

Understanding multiple cloning strategies also strengthens core graph traversal skills (DFS, BFS) and the use of hash maps to track visited nodes.

Approaches and Solutions

All three solutions use a hash map (dictionary) that maps original nodes to their cloned counterparts. This map serves two purposes: it prevents infinite recursion/loops in cyclic graphs and ensures each node is cloned exactly once. The differences lie in how we traverse the graph.

Solution 1: DFS Recursive with HashMap

The recursive DFS approach is the most intuitive. We clone the current node, then recursively clone all its neighbors, adding the cloned neighbors to the clone’s neighbor list.

// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<>();
    }
    public Node(int _val, List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> visited = new HashMap<>();
    return dfs(node, visited);
}

private Node dfs(Node node, Map<Node, Node> visited) {
    if (visited.containsKey(node)) {
        return visited.get(node);
    }
    // Create clone for current node
    Node clone = new Node(node.val);
    visited.put(node, clone);
    // Recursively clone neighbors
    for (Node neighbor : node.neighbors) {
        clone.neighbors.add(dfs(neighbor, visited));
    }
    return clone;
}

Explanation: The visited map holds the mapping from original node to its clone. When we encounter a node already in the map, we return the existing clone, preventing cycles from causing infinite recursion. The recursion depth equals the depth of the graph (longest path from the start node).

Solution 2: DFS Iterative (Stack)

This approach eliminates recursion by using an explicit stack. It mimics the call stack of the recursive version.

public Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> visited = new HashMap<>();
    Stack<Node> stack = new Stack<>();
    stack.push(node);
    visited.put(node, new Node(node.val));
    
    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        Node cloneCur = visited.get(cur);
        for (Node neighbor : cur.neighbors) {
            if (!visited.containsKey(neighbor)) {
                visited.put(neighbor, new Node(neighbor.val));
                stack.push(neighbor);
            }
            cloneCur.neighbors.add(visited.get(neighbor));
        }
    }
    return visited.get(node);
}

Explanation: We start by cloning the root node and pushing it onto the stack. In each iteration, we pop a node, retrieve its clone, and process its neighbors. For any neighbor not yet cloned, we clone it, push the original onto the stack, and then add the cloned neighbor to the current clone’s neighbor list. The stack ensures we eventually process all reachable nodes in a depth-first order.

Solution 3: BFS (Queue)

Breadth-first traversal uses a queue. It processes nodes level by level, which can be more intuitive for graphs with wide branching.

public Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> visited = new HashMap<>();
    Queue<Node> queue = new LinkedList<>();
    queue.offer(node);
    visited.put(node, new Node(node.val));
    
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        Node cloneCur = visited.get(cur);
        for (Node neighbor : cur.neighbors) {
            if (!visited.containsKey(neighbor)) {
                visited.put(neighbor, new Node(neighbor.val));
                queue.offer(neighbor);
            }
            cloneCur.neighbors.add(visited.get(neighbor));
        }
    }
    return visited.get(node);
}

Explanation: The queue holds original nodes whose clones have been created but whose neighbors may not have been fully processed. For each node polled, we iterate over its neighbors. If a neighbor hasn’t been cloned yet, we create its clone, add it to the map, and enqueue the original neighbor. Then we add the cloned neighbor to the current clone’s list. BFS guarantees that we clone nodes in increasing distance from the start node.

Complexity Analysis

All three solutions share the same asymptotic time and space complexity:

Time Complexity: O(V + E) – Each vertex is visited once, and each edge is traversed once (since we process each neighbor list).
Space Complexity: O(V) – The visited map stores one entry per vertex. Additionally:
- DFS Recursive: O(V) for the recursion stack in the worst case (e.g., a linear chain graph).
- DFS Iterative: O(V) for the explicit stack (worst-case depth).
- BFS: O(V) for the queue (worst-case breadth, e.g., a star graph).

In practice, recursion may cause stack overflow for very deep graphs (e.g., a long chain of 10^5 nodes). Iterative DFS or BFS avoid that risk. BFS also has the advantage of using a queue, which often performs slightly better in languages with deep recursion limitations.

Best Practices

Always use a map (hash table) to track visited nodes. This is mandatory for cyclic graphs and ensures O(1) lookup for already-cloned nodes.
Handle the null case explicitly. Return null if the input node is null.
Prefer iterative approaches for production code when graph depth is unknown or potentially large, to avoid stack overflow errors.
Understand the difference between shallow and deep copy. A shallow copy would copy the node object but share neighbor references with the original – that is not the goal here.
Use appropriate data structures: HashMap for the mapping, Stack or LinkedList (Queue) for traversal. Avoid recursion for deep graphs.
Test with edge cases: single node (no neighbors), disconnected graph, graph with cycles, and large graphs to verify performance.
Write clear code with descriptive variable names (e.g., visited, cloneCur) to improve readability and maintainability.

Conclusion

Cloning a graph is a classic graph problem that tests your understanding of traversal algorithms and deep copying. The recursive DFS approach is elegant and easy to implement for small to moderate graphs, while the iterative DFS and BFS variants offer better safety against stack overflows and are equally efficient. All three solutions run in O(V+E) time and O(V) space, making them optimal for this task. By mastering these patterns, you not only solve the clone graph problem but also build a strong foundation for handling more complex graph operations such as serialization, copy-on-write, and concurrent graph processing.