Overview

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

Each node has a val (integer) and a neighbors array (list of adjacent nodes). Your clone must create entirely new node objects — no references to the original graph should remain.

Constraints

• The graph has 1 to 100 nodes.
• 1 <= val <= 100 and all values are unique.
• No self-loops or repeated edges.
• The graph is connected.
• Input/output uses adjacency list representation: { val, neighbors: [...] }.

Examples

// Graph: 1 -- 2
//        |    |
//        4 -- 3

// Input adjacency list: [[2,4],[1,3],[2,4],[1,3]]
// Node 1 neighbors: [2, 4]
// Node 2 neighbors: [1, 3]
// etc.

cloneGraph(node1);
// => deep copy of the entire graph

Solution

function cloneGraph(node) {
  if (!node) return null;
  const visited = new Map();

  function dfs(n) {
    if (visited.has(n.val)) return visited.get(n.val);
    const clone = { val: n.val, neighbors: [] };
    visited.set(n.val, clone);
    for (const neighbor of n.neighbors) {
      clone.neighbors.push(dfs(neighbor));
    }
    return clone;
  }

  return dfs(node);
}

Resources

• Clone Graph — LeetCode
• Graph Theory — Wikipedia