Clone Graph

Approach Summary

BFS/DFS with a hash map from original node to its clone. On each visit, create clone if not exists, then clone neighbors.

Full Solution & Approach

Cloning a graph means building a deep copy while preserving the connection structure — every node must become a fresh node, and edges must map to edges between the clones. Use a hash map from original node to clone so each node is created exactly once. BFS from the original start node: for each node dequeued, look up (or create) its clone, then for each neighbor create its clone on demand and connect the neighbor-clone into the current clone's neighbors list. Because the map is checked before creating, cyclic graphs terminate correctly — a back edge simply returns the already-created clone. The recursion-free BFS version avoids stack-overflow risk on deep graphs. The map from original to clone is the invariant that makes the copy a true deep copy and not a shared reference.

Each node and edge is visited once — O(V + E) time. The hash map stores one clone per node and the queue holds the frontier — O(V) space.

Solution Code

Solution

from collections import deque

def clone_graph(node):
    if not node:
        return None
    clones = {node: Node(node.val)}
    queue = deque([node])
    while queue:
        cur = queue.popleft()
        for neighbor in cur.neighbors:
            if neighbor not in clones:
                clones[neighbor] = Node(neighbor.val)
                queue.append(neighbor)
            clones[cur].neighbors.append(clones[neighbor])
    return clones[node]

function cloneGraph(node) {
  if (!node) return null;
  const clones = new Map([[node, new Node(node.val)]]);
  const queue = [node];
  for (let qi = 0; qi < queue.length; qi++) {
    const cur = queue[qi];
    for (const neighbor of cur.neighbors) {
      if (!clones.has(neighbor)) {
        clones.set(neighbor, new Node(neighbor.val));
        queue.push(neighbor);
      }
      clones.get(cur).neighbors.push(clones.get(neighbor));
    }
  }
  return clones.get(node);
}

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

Node* cloneGraph(Node* node) {
    if (!node) return nullptr;
    unordered_map<Node*, Node*> clones;
    clones[node] = new Node(node->val);
    queue<Node*> q;
    q.push(node);
    while (!q.empty()) {
        Node* cur = q.front(); q.pop();
        for (Node* neighbor : cur->neighbors) {
            if (!clones.count(neighbor)) {
                clones[neighbor] = new Node(neighbor->val);
                q.push(neighbor);
            }
            clones[cur]->neighbors.push_back(clones[neighbor]);
        }
    }
    return clones[node];
}

Edge Cases to Watch

Empty graph — return null
Single node with no neighbors
Self-loop — the node is its own neighbor; the map handles it
Dense graph — every edge maps to its clone pair

How to Recognize This Pattern

Deep copy of graph
Map from original to clone

Complexity Analysis

Time Complexity

O(V + E)

Space Complexity

O(V)