Clone Graph Visualizer & Step-by-Step Algorithm Solution

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph using DFS recursion and a hash map to cache visited clones.

Category: graphs | Difficulty: Medium

Tags: Graph, DFS, Hash Table, Recursion, Deep Copy

Clone Graph

Drag nodes to arrange
ORIGINAL GRAPH (Left) ➔ CLONED GRAPH (Right)
1
2
3
4
VISITED CLONE MAP (Node ➔ Clone)
(Empty Map)
100%
state
active-
cloned0 of 4
clonedEdges0
Initialization
1/54
Explanation

Start cloneGraph on connected graph with 4 vertices. Cloned graph and visited map are currently empty.

Source Code
1function cloneGraph(node) {
2 if (!node) return null;
3 const map = new Map();
4 function dfs(curr) {
5 if (map.has(curr)) return map.get(curr);
6 const clone = new Node(curr.val);
7 map.set(curr, clone);
8 for (const neighbor of curr.neighbors) {
9 clone.neighbors.push(dfs(neighbor));
10 }
11 return clone;
12 }
13 return dfs(node);
14}