Clone Graph

Make a deep copy of a connected graph.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Clone Graph: Create one mapped copy per original node, then reproduce every adjacency entry between copies.

Input and goalMake a deep copy of a connected graph.

Create the first copyFor triangle O1-O2-O3, create C1 before traversal and enqueue O1. The map is {O1:C1}.

frontierO1

currentO1copiesO1->C1

Recognize it

A cyclic connected object must be deep-copied while preserving adjacency, so each original identity needs exactly one reusable copied identity before edges are wired.

Keep true

Every key in copies maps to exactly one clone, and after an original node is processed, its clone has one copied neighbor entry for every original neighbor processed in order.

Reuse it

When copying any cyclic object graph, allocate and memoize an object before traversing its references, then resolve every copied reference through that memo.

Pattern: Graph traversal plus a map from old nodes to copied nodes.

Simple idea: The map has two jobs. It prevents repeated work and gives the copy of every neighbor when building copied edges.

from __future__ import annotations
from collections import deque

class GraphNode:
   def __init__(self, val: int = 0, neighbors: list[GraphNode] | None = None) -> None:
      self.val = val
      self.neighbors = neighbors or []


def clone_graph(node: GraphNode | None) -> GraphNode | None:
   if node is None:
      return None

   copies = {node: GraphNode(node.val)}
   queue = deque([node])

   while queue:
      current = queue.popleft()
      for neighbor in current.neighbors:
         if neighbor not in copies:
            copies[neighbor] = GraphNode(neighbor.val)
            queue.append(neighbor)
         copies[current].neighbors.append(copies[neighbor])
   return copies[node]

Cost: $O(V+E)$ time and $O(V)$ space.