Clone a graph
Problem
Given a reference to one node of a connected undirected graph (each node has a value and a list of neighbours), return a deep copy of the whole graph.
Example 1
Input: adjacency = [[2,4], [1,3], [2,4], [1,3]] Output: A new graph with the same structure
Also asked as: Clone a graph
Test cases
Case 1
Input: [[2,4],[1,3],[2,4],[1,3]] Expected: [[2,4],[1,3],[2,4],[1,3]]
Case 2
Input: [[]] Expected: [[]]
Case 3
Input: [] Expected: []
View solutionHide solution1 approach
1. DFS/BFS with an original → copy map
Time O(V + E)Space O(V)
On first visit, create the copy and store it; for each neighbour, recurse (creating it if needed) and link.
function cloneGraph(node) { if (!node) return null; const map = new Map(); const dfs = (n) => { if (map.has(n)) return map.get(n); const copy = { val: n.val, neighbors: [] }; map.set(n, copy); for (const nb of n.neighbors) copy.neighbors.push(dfs(nb)); return copy; }; return dfs(node);}