Clone Graph

mediumGraphs: BFS / DFS62 stepsJava · Python · C++

Deep-copy a connected undirected graph. DFS through the original; a map from original node to its copy both prevents infinite loops on cycles and lets each copy link to the copies of its neighbours.

▶ Watch the animated trace

Traced input: adjList = [[2, 4], [1, 3], [2, 4], [1, 3]] → [[2, 4], [1, 3], [2, 4], [1, 3]]. Original problem: neetcode.io/problems/clone-graph

Complexity

BestO(V + E)

AverageO(V + E)

WorstO(V + E)

SpaceO(V)

Each node is copied once and each edge followed twice.

Key idea

The map old → copy doubles as the visited set.
Create the copy before recursing into neighbours, so cycles find it in the map.
Each copy's neighbour list holds copies, never originals.

Common mistakes

Recursing before storing the copy in the map loops forever on cycles.
Returning original nodes inside the clone's neighbour lists.
Not handling a null input.

Solution

Java

class Node {
    int val;
    List<Node> neighbors = new ArrayList<>();
    Node(int v) { val = v; }
}

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

Node clone(Node node, Map<Node, Node> copies) {
    if (node == null) return null;
    if (copies.containsKey(node)) return copies.get(node);
    Node copy = new Node(node.val);
    copies.put(node, copy);
    for (Node nb : node.neighbors) {
        copy.neighbors.add(clone(nb, copies));
    }
    return copy;
}

Python

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


def cloneGraph(node: Optional["Node"]) -> Optional["Node"]:
    copies = {}

    def clone(n):
        if n in copies: return copies[n]
        copy = Node(n.val)
        copies[n] = copy
        for nb in n.neighbors:
            copy.neighbors.append(clone(nb))
        return copy

    return clone(node) if node else None

C++

class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node(int v) : val(v) {}
};

Node* clone(Node* node, unordered_map<Node*, Node*>& copies) {
    if (!node) return nullptr;
    if (copies.count(node)) return copies[node];
    Node* copy = new Node(node->val);
    copies[node] = copy;
    for (Node* nb : node->neighbors) {
        copy->neighbors.push_back(clone(nb, copies));
    }
    return copy;
}

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

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single node, no edges Copy one node with an empty neighbour list.	`adjList = [[]]`	`[[]]`
Empty graph Return null.	`adjList = []`	`[]`
Two nodes The cycle 1 → 2 → 1 is handled by the map.	`adjList = [[2], [1]]`	`[[2], [1]]`