Clone a graph

Medium

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: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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);
}