Clone Graph

Recurse from the start node. Before recursing into a neighbor, check the map: if we have already begun cloning that node, reuse the existing clone instead of recursing again (this is what breaks cycles).

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

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None

        cloned = {}  # original node -> its clone

        def dfs(n):
            if n in cloned:
                return cloned[n]
            copy = Node(n.val)
            cloned[n] = copy  # register BEFORE recursing, so cycles terminate
            for neighbor in n.neighbors:
                copy.neighbors.append(dfs(neighbor))
            return copy

        return dfs(node)

Watch the clone map: a clone is registered the instant it is created, and every neighbor lookup that hits an already-registered entry is the recursion guard stopping a re-descent. The left panel is the original graph, the middle column is the clone map, and the right panel grows into the deep copy (indigo = current dfs call, amber = the neighbor being looked up, slate = already cloned, emerald = fresh clone).

Every node is registered in the map the instant its clone is created, so re-entering it (because the graph has a cycle) is a cheap lookup, not a re-clone. Correctness: each original node maps to exactly one clone, and every edge in the original graph is mirrored between the corresponding clones. Complexity: each node is cloned once and each edge is traversed once → O(V + E) time; the map and the recursion stack both hold up to V entries → O(V + E) space counting the output graph itself.

Same idea, iterative: seed the map with a clone of the start node, then process nodes from a queue. This avoids recursion depth entirely, which matters if the graph is large or has a long path before the last unvisited node.

from collections import deque

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None

        cloned = {node: Node(node.val)}
        queue = deque([node])

        while queue:
            curr = queue.popleft()
            for neighbor in curr.neighbors:
                if neighbor not in cloned:
                    cloned[neighbor] = Node(neighbor.val)
                    queue.append(neighbor)
                cloned[curr].neighbors.append(cloned[neighbor])

        return cloned[node]

Same trace, BFS order: start by cloning 1 and enqueuing it. Pop 1, see neighbors 2 and 4 — both unseen, so clone and enqueue both, and wire 1'.neighbors = [2', 4']. Pop 2, see neighbors 1 (already cloned, just wire the edge) and 3 (clone, enqueue, wire). Pop 4, see neighbors 1 (wire) and 3 (already cloned by now, just wire). Pop 3, see neighbors 2 and 4 (both already cloned, just wire both edges). Queue empties with all 4 nodes cloned and every edge mirrored.

Why it’s the preferred version: identical time and space complexity to the DFS version, but the traversal is explicit (a queue) instead of hidden in the call stack, so there’s no risk of hitting Python’s recursion limit on graphs with long chains. Complexity: every node is enqueued once and every edge is inspected once → O(V + E) time, O(V + E) space for the map, queue, and output graph.