Clone Graph

Copying a tree is easy: copy the node, then copy its children. Try the same on a graph and it never ends, because a graph has cycles — in an undirected graph, every edge is a two-node cycle. This problem is about noticing that, and about the one data structure that fixes it.

The problem

You are given one node of a connected, undirected graph. Each node has an integer val and a list neighbors. Return a deep copy of the whole graph: new node objects, with the same values and the same connections, sharing nothing with the original.

Example. The graph has four nodes: 1 connects to 2 and 3; 2 connects to 1 and 3; 3 connects to 1, 2 and 4; 4 connects to 3. As adjacency lists: [[2, 3], [1, 3], [1, 2, 4], [3]].

Output: a copy of node 1 whose neighbours are copies of 2 and 3, and so on — four new nodes in total, with the same lists. Nodes 1, 2 and 3 form a triangle, so the copy must also contain that triangle, not three separate chains.

Constraints. Up to 10^4 nodes; values are unique, from 1 to n. The given node may be None (an empty graph).

1class Node:2    """A graph node: a value and the list of its neighbours."""34    def __init__(self, val: int, neighbors: list["Node"] | None = None) -> None:5        self.val = val6        self.neighbors: list[Node] = neighbors if neighbors is not None else []

Clarifying questions

• Is the graph connected? Yes — every node is reachable from the one given.
• Does neighbour order matter? Keep the same order; it makes the copy easy to check.
• Can there be self-loops or repeated edges? Assume not, though the solution below handles them.
• What about an empty graph? Return None.

Approach 1: the simple way

Copy the node, then recursively copy each neighbour — exactly how you would copy a tree.

1def clone_naive(node: Node | None) -> Node | None:2    """Copy a node and recursively copy its neighbours. Never terminates on a cycle."""3    if node is None:4        return None5    copy = Node(node.val)6    for nb in node.neighbors:7        copy.neighbors.append(clone_naive(nb))8    return copy

On the example, clone_naive(1) copies neighbour 2, which copies its neighbour 1, which copies 2 again, forever. Python stops it with RecursionError. It is not slow; it is wrong. Even on a graph with no cycles, a node reachable by two routes would be copied twice, and the copy would no longer be the same shape. The only graph it handles is a single node with no edges.

The key insight

The problem is that the code cannot answer one question: have I already copied this node? Answer it with a dictionary from each original node to its copy.

That dictionary does two jobs at once. It is the visited set — a node in the dictionary is never copied again, so cycles end. And it is the lookup for shared nodes — when node 3 needs a neighbour 1, it gets the same copy of 1 that node 2 got, so the triangle stays a triangle.

One detail decides whether it works: register the copy in the dictionary before copying its neighbours. The neighbours will loop back to this node, and at that moment the copy must already be findable.

Approach 2: DFS with a map

1def clone_graph(node: Node | None) -> Node | None:2    """Deep copy of a connected graph, DFS with an original-to-copy map."""3    if node is None:4        return None5    copies: dict[Node, Node] = {}67    def clone(original: Node) -> Node:8        if original in copies:9            return copies[original]              # already copied: reuse it10        copy = Node(original.val)11        copies[original] = copy                  # register BEFORE the neighbours12        for nb in original.neighbors:13            copy.neighbors.append(clone(nb))14        return copy1516    return clone(node)

Step by step:

1. clone(original) first looks in copies. If the node was copied, return that copy.
2. Otherwise make a new node and store it in copies immediately.
3. Then clone each neighbour and append the result, in the original order.

Dry run on the example, starting from node 1. Indentation shows recursion depth.

Four copies were made, one per node, and every later request returned an existing copy.

Complexity. Time O(V + E): each node is copied once, and each edge is followed once from each end. Space O(V) for the map, plus the recursion depth, which can reach V.

Approach 3: BFS, no recursion

That recursion depth is a real problem at 10^4 nodes. A graph shaped like a long chain makes the DFS 10^4 calls deep, and Python's default limit is about 1,000 — in testing, a 5,000-node chain raised RecursionError. The iterative BFS version has no such limit.

1from collections import deque234def clone_graph_bfs(node: Node | None) -> Node | None:5    """Same deep copy with a queue: no recursion depth limit."""6    if node is None:7        return None8    copies = {node: Node(node.val)}9    queue = deque([node])10    while queue:11        original = queue.popleft()12        for nb in original.neighbors:13            if nb not in copies:14                copies[nb] = Node(nb.val)        # create on discovery15                queue.append(nb)16            copies[original].neighbors.append(copies[nb])17    return copies[node]

The idea is the same. A copy is created the moment its original is discovered — the same "mark on push" rule as every BFS — and each popped node wires up its copy's neighbour list. The last line runs for every neighbour, new or not: the edge must be copied even when the node already exists.

Complexity. O(V + E) time and O(V) space, with no recursion.

Edge cases

• None input → return None.
• A single node with no neighbours → one new node with an empty list.
• A self-loop (a node in its own neighbour list) → the map already holds the node when the loop is followed, so the copy points at itself, as it should.
• Two nodes with the same value → the map is keyed by the node object, not by val, so this still works. Keying by val would break it.

Follow-ups

• "Copy a linked list where each node also has a random pointer." Same idea: a map from original to copy, then wire next and random through it. It can be done in O(1) extra space by interleaving copies into the list.
• "The graph may be disconnected, and you are given all nodes." Loop over every node and start a clone from each one not yet in the map, sharing the same map.
• "Check that the copy is correct." Traverse both graphs together and compare values and neighbour lists, and check that no copied node is also an original node (is comparison).