Clone Graph

Problem

Given a reference to a node in a connected, undirected graph, return a deep clone of the whole graph.

Constraints

• 0 ≤ Node.val ≤ 100
• 1 ≤ nodes ≤ 100

Approach — Graphs

This is a Graphs problem. The idea: explore the graph with BFS or DFS, marking nodes visited so you never process one twice. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(V + E) time.

Solution code

Python

class Solution:
    def cloneGraph(self, node):
        if not node:
            return None
        clones = {}
        def dfs(cur):
            if cur in clones:
                return clones[cur]
            copy = Node(cur.val)
            clones[cur] = copy
            for nb in cur.neighbors:
                copy.neighbors.append(dfs(nb))
            return copy
        return dfs(node)

Java

import java.util.*;

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        // BFS with a visited map (old node -> its clone). The map is
        // both the "already copied?" check and the wiring table.
        Map<Node, Node> clone = new HashMap<>();
        clone.put(node, new Node(node.val));
        Queue<Node> q = new ArrayDeque<>();
        q.add(node);
        while (!q.isEmpty()) {
            Node cur = q.poll();
            for (Node nb : cur.neighbors) {
                if (!clone.containsKey(nb)) {
                    clone.put(nb, new Node(nb.val));
                    q.add(nb);
                }
                clone.get(cur).neighbors.add(clone.get(nb));
            }
        }
        return clone.get(node);

        // DFS alternative: recurse and memoize the clone per node.
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.