⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#133) before relying on it.

Clone Graph

An interactive visualization of deep copying an undirected graph using DFS. Watch how each node is cloned and connections are rebuilt using a visited hash map.

DFS LeetCode 133 ↗ Medium

The Problem

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list of its neighbors (List[Node]). The graph is represented using an adjacency list where the index of each list element corresponds to the node's value (1-indexed).

The cloned graph must be a completely independent copy — modifying the clone must not affect the original.

Interactive Visualization

Preset

Speed:

Graph Visualization

Original Graph

Cloned Graph

Visited Hash Map

visited = { }

Code

fun cloneGraph(node: Node?): Node? {    if (node == null)        return null    val visited = HashMap<Node, Node>()    fun dfs(node: Node): Node {        if (node in visited)            return visited[node]!!        val clone = Node(node.`val`)        visited[node] = clone        for (neighbor in node.neighbors) {            clone.neighbors.add(dfs(neighbor!!))        }        // all neighbors processed        return clone    }    return dfs(node)}

def cloneGraph(node):    if not node:        return None    visited = {}    def dfs(node):        if node in visited:            return visited[node]        clone = Node(node.val)        visited[node] = clone        for neighbor in node.neighbors:            clone.neighbors.append(                dfs(neighbor)            )        return clone    return dfs(node)

Status

Press Step or Play to begin.

How It Works

Key Insight

DFS combined with a hash map (visited) prevents infinite loops in the graph and ensures each node is cloned exactly once. The hash map maps each original node to its clone, so when we encounter an already-visited neighbor, we simply return the cached clone instead of creating a duplicate.

The Algorithm

Base case: If the input node is None, return None.
Initialize: Create an empty visited dictionary to track cloned nodes.
DFS function: For each node:
- If already in visited, return the cached clone (prevents infinite recursion).
- Create a new Node with the same value.
- Store it in visited immediately (before processing neighbors).
- Recursively clone each neighbor and append to the clone's neighbor list.
Return: The clone of the starting node, which is connected to clones of all reachable nodes.

Complexity

Time O(V + E)

Space O(V)

We visit each node exactly once (V nodes) and traverse each edge exactly once (E edges). The space is O(V) for the visited hash map and the recursion stack (at most V deep in a degenerate graph).