Clone Graph: Deep-Copy a Connected Graph with a Hash Map and BFS or DFS

Problem

You are given one node of a connected, undirected graph. Each node has an integer value and a list of neighbours. Return a deep copy of the whole graph: new node objects with the same values and the same connections, sharing no node objects with the original. Return None for an empty graph.

This is widely known as LeetCode 133, “Clone Graph”.

Assume up to 100 nodes with unique values from 1 to 100.

Examples

A triangle with a tail:

  5 - 6
   \ /
    7 - 8

adjacency: 5:[6,7]  6:[5,7]  7:[5,6,8]  8:[7]
The clone has the same adjacency, but every node is a new object.

A single node with no neighbours: clone it alone.
Empty graph (None): return None.

Approach 1: two passes

Collect all nodes first, create copies, then wire the neighbours using a lookup by value.

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


def clone_graph_two_pass(node):
    if node is None:
        return None
    # Pass 1: find every node
    stack, seen = [node], {node}
    while stack:
        cur = stack.pop()
        for nb in cur.neighbors:
            if nb not in seen:
                seen.add(nb)
                stack.append(nb)
    # Pass 2: copy, then wire
    copies = {old: Node(old.val) for old in seen}
    for old, new in copies.items():
        new.neighbors = [copies[nb] for nb in old.neighbors]
    return copies[node]

It is also O(V + E), and it is a fine answer. The single-pass version below is what most interviewers expect.

Approach 2: optimal, one-pass BFS with an old-to-new map

Template

copies = {start: copy(start)}
queue = [start]
while queue:
    old = queue.pop_front()
    for nb in old.neighbours:
        if nb not in copies:             # first time seen
            copies[nb] = copy(nb)
            queue.append(nb)
        copies[old].neighbours.append(copies[nb])

Python solution

from collections import deque

def clone_graph(node):
    if node is None:
        return None
    copies = {node: Node(node.val)}
    queue = deque([node])
    while queue:
        old = queue.popleft()
        for nb in old.neighbors:
            if nb not in copies:
                copies[nb] = Node(nb.val)
                queue.append(nb)
            copies[old].neighbors.append(copies[nb])
    return copies[node]


def clone_graph_dfs(node, copies=None):
    """Recursive DFS version; fine for small graphs."""
    if node is None:
        return None
    if copies is None:
        copies = {}
    if node in copies:
        return copies[node]
    copy = Node(node.val)
    copies[node] = copy                  # register BEFORE recursing, or cycles loop forever
    copy.neighbors = [clone_graph_dfs(nb, copies) for nb in node.neighbors]
    return copy

Complexity

• Time: O(V + E). Each node is copied once and each adjacency entry is processed once.
• Space: O(V) for the map and the queue (O(V) recursion depth for the DFS version), plus the clone itself.

Tests

def build(adj):
    nodes = {v: Node(v) for v in adj}
    for v, nbs in adj.items():
        nodes[v].neighbors = [nodes[u] for u in nbs]
    return nodes

def to_adj(start):
    adj, seen, stack = {}, {start}, [start]
    while stack:
        cur = stack.pop()
        adj[cur.val] = [nb.val for nb in cur.neighbors]
        for nb in cur.neighbors:
            if nb not in seen:
                seen.add(nb); stack.append(nb)
    return adj

def all_nodes(start):
    seen, stack = {start}, [start]
    while stack:
        for nb in stack.pop().neighbors:
            if nb not in seen:
                seen.add(nb); stack.append(nb)
    return seen

shape = {5: [6, 7], 6: [5, 7], 7: [5, 6, 8], 8: [7]}
for fn in (clone_graph, clone_graph_dfs, clone_graph_two_pass):
    original = build(shape)[5]
    copy = fn(original)
    assert to_adj(copy) == shape                       # same structure (with a cycle)
    assert not (all_nodes(copy) & all_nodes(original))  # no shared objects
    assert fn(None) is None                             # empty graph
    lone = fn(Node(7))
    assert lone.val == 7 and lone.neighbors == []       # single node

# A two-node graph and a complete graph on 4 nodes
pair = {1: [2], 2: [1]}
assert to_adj(clone_graph(build(pair)[1])) == pair
k4 = {v: [u for u in range(1, 5) if u != v] for v in range(1, 5)}
assert to_adj(clone_graph(build(k4)[3])) == k4

Edge cases and pitfalls

• Registering the copy after recursing in DFS: a cycle returns to the node before it is in the map, and the recursion never ends.
• Keying the map by value works only when values are unique; keying by node object is always safe.
• Shallow copying the neighbour list (copy.neighbors = node.neighbors) points the clone back into the original.
• Empty input must return None, not raise.
• Disconnected graphs are not reachable from one node; if the input is a list of nodes, loop over all of them.

Where this shows up in data engineering

Copying a DAG definition (for example duplicating a pipeline template for a new tenant) has the same shape: walk the graph, map each old task to its new one, and rebuild the dependency edges through that map. The map is what keeps shared upstream tasks shared instead of duplicated.