Module 19 · Graph Traversal and Connected Components

185. Clone a Graph

Bridge · Download this solution · All solutions and shared helpers

Problem

Deep-copy every node reachable from a GraphNode reference, preserving values, neighbor order, repeated edges, cycles and self-loops. Return the corresponding cloned root, or None for None. Nodes with equal values remain distinct objects; no clone may reference an original node.

Examples

Example 1

a=GraphNode(7); a.neighbors=[a]; copy=clone_graph(a)
(copy is not a, copy.val, copy.neighbors[0] is copy)
=> (True, 7, True)

A self-loop points to the new object.

Example 2

clone_graph(None)
=> None

No root means no reachable graph.

Example 3

a=GraphNode(1); b=GraphNode(1); a.neighbors=[b]; b.neighbors=[a]; copy=clone_graph(a)
(copy.neighbors[0] is not copy, copy.neighbors[0].neighbors[0] is copy)
=> (True, True)

Equal values do not collapse two nodes in a cycle.

Reveal the worked solution and reasoning

Why this mechanism works

Allocate a node's copy as soon as that original is discovered, before following its edges. An identity-keyed mapping then provides a stable destination for back edges and shared neighbors. Every outgoing edge can append the already-known clone or trigger creation of a new one.

State and boundaries

copies maps each discovered original object to exactly one new object. The queue holds originals whose neighbor lists still need copying.

Protocol

Allocate and map the root copy.
Pop an original.
For each neighbor create its copy if absent and enqueue it.
Append that mapped copy to the current clone's neighbors.
Return the mapped root.

Visualization

original A -> B -> A
create A' first; map A:A'
create B'; edge A'->B'
back edge B'->copies[A] closes the clone cycle

Python implementation

from collections import deque
from structures import GraphNode

def clone_graph(root):
    if root is None:
        return None
    copies = {root: GraphNode(root.val)}
    queue = deque([root])
    while queue:
        original = queue.popleft()
        for neighbor in original.neighbors:
            if neighbor not in copies:
                copies[neighbor] = GraphNode(neighbor.val)
                queue.append(neighbor)
            copies[original].neighbors.append(copies[neighbor])
    return copies[root]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

(copy is not a, copy.val, copy.neighbors[0] is copy)

L5 clone_graph: if root is None:
root=N1(val=7,neighbors=[N1])

L7 clone_graph: copies = {root: GraphNode(root.val)}
root=N1(val=7,neighbors=[N1]); copies={N1(val=7,neighbors=[N1]):N2(val=7,neighbors=[])}

L8 clone_graph: queue = deque([root])
root=N1(val=7,neighbors=[N1]); copies={N1(val=7,neighbors=[N1]):N2(val=7,neighbors=[])}; queue=deque([N1(val=7,neighbors=[N1])])

L10 clone_graph: original = queue.popleft()
root=N1(val=7,neighbors=[N1]); copies={N1(val=7,neighbors=[N1]):N2(val=7,neighbors=[])}; queue=deque([]); original=N1(val=7,neighbors=[N1])

L11 clone_graph: for neighbor in original.neighbors:
root=N1(val=7,neighbors=[N1]); copies={N1(val=7,neighbors=[N1]):N2(val=7,neighbors=[])}; queue=deque([]); original=N1(val=7,neighbors=[N1]); neighbor=N1(val=7,neighbors=[N1])

L15 clone_graph: copies[original].neighbors.append(copies[neighbor])
root=N1(val=7,neighbors=[N1]); copies={N1(val=7,neighbors=[N1]):N2(val=7,neighbors=[N2])}; queue=deque([]); original=N1(val=7,neighbors=[N1]); neighbor=N1(val=7,neighbors=[N1])

Result: (True, 7, True). A self-loop points to the new object.

clone_graph(None)

L5 clone_graph: if root is None:
root=None

Result: None. No root means no reachable graph.

Why the solution is correct

The map guarantees a one-to-one copy for every discovered original. Each original adjacency entry becomes an entry to the corresponding clone in the same order. All reachable originals are eventually processed, so all edges and values are copied without retaining original references.

Time and space

O(V+E) time, O(V) auxiliary map/queue space, and O(V+E) newly allocated graph output.

Common mistakes

Mapping by value merges distinct equal-valued nodes. Allocating only after recursively exploring neighbors fails on cycles.

Reasoning card

State: copies maps each discovered original object to exactly one new object. The queue holds originals whose neighbor lists still need copying.

Invariant: Every original discovered so far has one stable copy.

Decision to rehearse: Map original nodes to copies before exploring neighbours.

Finish: Return the mapped root

Transfer exercise

Serialize the reachable graph with explicit node IDs, then explain why values alone cannot serve as those IDs.