Clone Graph

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.

class Node {
    public int val;
    public List<Node> neighbors;
}

Test case format:

For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]] Explanation: There are 4 nodes in the graph. 1st node (val = 1)‘s neighbors are 2nd node (val = 2) and 4th node (val = 4). 2nd node (val = 2)‘s neighbors are 1st node (val = 1) and 3rd node (val = 3). 3rd node (val = 3)‘s neighbors are 2nd node (val = 2) and 4th node (val = 4). 4th node (val = 4)‘s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:

Input: adjList = [[]] Output: [[]] Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3:

Input: adjList = [] Output: [] Explanation: This an empty graph, it does not have any nodes.

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 can be visited starting from the given node.

Approach: DFS with Hash Map (Optimal Solution)

Algorithm

1. Use a hash map map that records the correspondence between each original node and its copy
2. Define dfs(node) that returns the clone of node
3. In dfs:
   • If node is null, return null
   • If node is already in the map, return its clone (avoid duplicate creation)
   • Otherwise, create a new node with the same value, register it in the map, and clone all neighbors recursively into its neighbor list
   • Return the clone
4. Return dfs(node) for the given starting node

Key Insight

A graph can have cycles, so a naive recursive clone would loop forever. Registering the clone in the map before recursing into neighbors breaks the cycle: when the recursion comes back to an already-cloned node, it returns the existing copy instead of creating a new one.

Time & Space Complexity

• Time Complexity: O(n) - each node and edge is visited once
• Space Complexity: O(n) - the hash map plus recursion stack

Java Implementation

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public class CloneGraph {

    private Map<Node, Node> map = new HashMap<>();

    public Node cloneGraph(Node node) {
        return dfs(node);
    }

    private Node dfs(Node node) {
        if (node == null) {
            return null;
        }
        Node clone = map.get(node);
        if (clone != null) {
            return clone;
        }
        clone = new Node(node.val);
        map.put(node, clone); // register before recursion to handle cycles
        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(dfs(neighbor));
        }
        return clone;
    }
}

Example Walkthrough

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

1. dfs(1): not in map → create clone 1, register it, clone neighbors
2. dfs(2): create clone 2, register, clone neighbors 1 and 3
3. dfs(1): already in map → return existing clone 1 (cycle broken)
4. dfs(3): create clone 3, register, clone neighbors 2 and 4
5. dfs(2): already in map → return existing clone 2
6. dfs(4): create clone 4, register, clone neighbors 1 and 3
7. Both 1 and 3 are already in the map → return their clones
8. Result: a complete deep copy of all 4 nodes with matching edges

Alternative Approach: BFS

import java.util.ArrayDeque;
import java.util.Deque;

public class CloneGraphBfs {

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

The BFS variant processes the graph level by level with an explicit queue, cloning each node the first time it is discovered and wiring up its neighbors.

Key Insights

1. Register Before Recurse: Putting the clone in the map before cloning neighbors is what prevents infinite loops on cycles
2. Deep Copy: Every node and every edge is duplicated — no shared references between original and clone
3. Single Source: Because the graph is connected, starting DFS from the given node reaches everything
4. Unique Values: Unique Node.val allows the map keyed on nodes to work reliably

The DFS with hash map is the optimal solution, providing O(n) time and O(n) space.