Skip to content

Clone Graph

Problem

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains a val and a list of its neighbors.

Approach

BFS with a hash map mapping original nodes to their clones. For each node dequeued, iterate its neighbors: clone unseen neighbors, then wire the cloned neighbor into the clone's neighbor list.

When to Use

Graph deep copy — "clone graph", "copy linked structure with cycles". BFS/DFS with a hash map from original to clone prevents revisiting. Also: snapshotting mutable graph state, undo/redo systems.

Complexity
Time O(V + E)
Space O(V)

Implementation

clone_graph

Deep copy an undirected graph.

Problem

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains a val and a list of its neighbors.

Approach

BFS with a hash map mapping original nodes to their clones. For each node dequeued, iterate its neighbors: clone unseen neighbors, then wire the cloned neighbor into the clone's neighbor list.

When to use

Graph deep copy — "clone graph", "copy linked structure with cycles". BFS/DFS with a hash map from original to clone prevents revisiting. Also: snapshotting mutable graph state, undo/redo systems.

Complexity

Time: O(V + E) Space: O(V)

GraphNode

Node in an undirected graph.

Source code in src/algo/graphs/clone_graph.py 
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class GraphNode:
    """Node in an undirected graph."""

    def __init__(
        self,
        val: int = 0,
        neighbors: list[GraphNode] | None = None,
    ) -> None:
        self.val = val
        self.neighbors: list[GraphNode] = neighbors if neighbors is not None else []

    def __repr__(self) -> str:
        neighbor_vals = [n.val for n in self.neighbors]
        return f"GraphNode({self.val}, neighbors={neighbor_vals})"

clone_graph 

clone_graph(node: GraphNode | None) -> GraphNode | None

Return a deep copy of the graph rooted at node.

n1 = GraphNode(1) ... n2 = GraphNode(2) n1.neighbors = [n2] ... n2.neighbors = [n1] c = clone_graph(n1) c is not n1 and c is not None and c.val == 1 True

Source code in src/algo/graphs/clone_graph.py 
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
def clone_graph(node: GraphNode | None) -> GraphNode | None:
    """Return a deep copy of the graph rooted at *node*.

    >>> n1 = GraphNode(1)
    ... n2 = GraphNode(2)
    >>> n1.neighbors = [n2]
    ... n2.neighbors = [n1]
    >>> c = clone_graph(n1)
    >>> c is not n1 and c is not None and c.val == 1
    True
    """
    if node is None:
        return None

    clones: dict[GraphNode, GraphNode] = {node: GraphNode(node.val)}
    queue: deque[GraphNode] = deque([node])

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

    return clones[node]
tests/graphs/test_clone_graph.py
"""Tests for clone graph."""

from algo.graphs.clone_graph import GraphNode, clone_graph


def _build_graph(adj: dict[int, list[int]]) -> dict[int, GraphNode]:
    """Build a graph from an adjacency dict and return node map."""
    nodes: dict[int, GraphNode] = {v: GraphNode(v) for v in adj}
    for v, neighbors in adj.items():
        nodes[v].neighbors = [nodes[n] for n in neighbors]
    return nodes


class TestCloneGraph:
    def test_none_input(self) -> None:
        assert clone_graph(None) is None

    def test_single_node(self) -> None:
        node = GraphNode(1)
        cloned = clone_graph(node)
        assert cloned is not None
        assert cloned is not node
        assert cloned.val == 1
        assert cloned.neighbors == []

    def test_two_nodes(self) -> None:
        n1, n2 = GraphNode(1), GraphNode(2)
        n1.neighbors = [n2]
        n2.neighbors = [n1]
        cloned = clone_graph(n1)
        assert cloned is not None
        assert cloned.val == 1
        assert len(cloned.neighbors) == 1
        assert cloned.neighbors[0].val == 2
        assert cloned is not n1
        assert cloned.neighbors[0] is not n2

    def test_triangle(self) -> None:
        nodes = _build_graph({1: [2, 3], 2: [1, 3], 3: [1, 2]})
        cloned = clone_graph(nodes[1])
        assert cloned is not None
        assert cloned.val == 1
        neighbor_vals = sorted(n.val for n in cloned.neighbors)
        assert neighbor_vals == [2, 3]

    def test_deep_copy_identity(self) -> None:
        """Cloned nodes must be distinct objects."""
        nodes = _build_graph({1: [2], 2: [1]})
        cloned = clone_graph(nodes[1])
        assert cloned is not None
        original_ids = {id(n) for n in nodes.values()}
        clone_ids: set[int] = set()
        visited: set[int] = set()
        stack = [cloned]
        while stack:
            n = stack.pop()
            nid = id(n)
            if nid in visited:
                continue
            visited.add(nid)
            clone_ids.add(nid)
            stack.extend(n.neighbors)
        assert original_ids.isdisjoint(clone_ids)

    def test_four_node_cycle(self) -> None:
        nodes = _build_graph({1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]})
        cloned = clone_graph(nodes[1])
        assert cloned is not None
        assert cloned.val == 1
        assert len(cloned.neighbors) == 2

Implement it yourself

Run: just challenge graphs clone_graph

Then implement the functions to make all tests pass. Use just study graphs for watch mode.

Reveal Solution

clone_graph

Deep copy an undirected graph.

Problem

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains a val and a list of its neighbors.

Approach

BFS with a hash map mapping original nodes to their clones. For each node dequeued, iterate its neighbors: clone unseen neighbors, then wire the cloned neighbor into the clone's neighbor list.

When to use

Graph deep copy — "clone graph", "copy linked structure with cycles". BFS/DFS with a hash map from original to clone prevents revisiting. Also: snapshotting mutable graph state, undo/redo systems.

Complexity

Time: O(V + E) Space: O(V)

GraphNode

Node in an undirected graph.

Source code in src/algo/graphs/clone_graph.py 
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class GraphNode:
    """Node in an undirected graph."""

    def __init__(
        self,
        val: int = 0,
        neighbors: list[GraphNode] | None = None,
    ) -> None:
        self.val = val
        self.neighbors: list[GraphNode] = neighbors if neighbors is not None else []

    def __repr__(self) -> str:
        neighbor_vals = [n.val for n in self.neighbors]
        return f"GraphNode({self.val}, neighbors={neighbor_vals})"

clone_graph 

clone_graph(node: GraphNode | None) -> GraphNode | None

Return a deep copy of the graph rooted at node.

n1 = GraphNode(1) ... n2 = GraphNode(2) n1.neighbors = [n2] ... n2.neighbors = [n1] c = clone_graph(n1) c is not n1 and c is not None and c.val == 1 True

Source code in src/algo/graphs/clone_graph.py 
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
def clone_graph(node: GraphNode | None) -> GraphNode | None:
    """Return a deep copy of the graph rooted at *node*.

    >>> n1 = GraphNode(1)
    ... n2 = GraphNode(2)
    >>> n1.neighbors = [n2]
    ... n2.neighbors = [n1]
    >>> c = clone_graph(n1)
    >>> c is not n1 and c is not None and c.val == 1
    True
    """
    if node is None:
        return None

    clones: dict[GraphNode, GraphNode] = {node: GraphNode(node.val)}
    queue: deque[GraphNode] = deque([node])

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

    return clones[node]