Solving Clone Graph in JavaScript: Step-by-Step Guide

Introduction to Clone Graph

The Clone Graph problem is a classic algorithmic challenge frequently encountered in coding interviews and real-world applications involving graph manipulation. Given a reference to a node in a connected undirected graph, the task is to return a deep copy (clone) of the entire graph. Each node in the graph contains a value and a list of references to its neighbors.

While the problem statement sounds simple, it tests a developer's understanding of graph traversal, memory references, and the subtle distinction between shallow and deep copying. In JavaScript, where objects are passed by reference, failing to handle cloning correctly can lead to shared references and unintended mutations.

Problem Definition

Formally, you are given a node class defined as follows:

function Node(val, neighbors) {
  this.val = val === undefined ? 0 : val;
  this.neighbors = neighbors === undefined ? [] : neighbors;
}

Your function receives a starting node (or null if the graph is empty) and must return the cloned starting node. The cloned graph must have the same structure and values as the original, but every node must be a brand-new object in memory.

Why Clone Graph Matters

Understanding how to clone a graph goes beyond passing interviews. It has practical implications in several areas of software development:

• Immutable data handling: When working with state management libraries (like Redux), you often need deep copies of complex nested structures to avoid mutating the original state.
• Graph-based applications: Social networks, recommendation engines, and dependency graphs frequently require duplicating subgraphs for parallel processing or simulation.
• Versioning and undo systems: Cloning allows you to snapshot a graph's state before modifications, enabling rollback functionality.
• Testing and debugging: Creating isolated copies of data structures helps in writing predictable unit tests.

The core challenge is handling cycles. In a graph, nodes can reference each other in circular ways, so a naive recursive copy would result in infinite loops. A robust solution must track visited nodes to avoid revisiting them.

Approaches to Solve Clone Graph

There are two primary traversal strategies to clone a graph: Depth-First Search (DFS) and Breadth-First Search (BFS). Both rely on a hash map (or JavaScript Map) to record mappings from original nodes to their clones, ensuring each node is only cloned once.

Approach 1: DFS with Recursion

The DFS approach recursively visits each node, creates a clone, and then recursively clones all its neighbors. The hash map serves two purposes: it prevents infinite recursion on cycles and provides quick lookup when wiring up neighbor references.

function cloneGraphDFS(node) {
  if (!node) return null;

  const visited = new Map();

  function dfs(currentNode) {
    // If already cloned, return the existing clone
    if (visited.has(currentNode)) {
      return visited.get(currentNode);
    }

    // Create a new node with the same value
    const clone = new Node(currentNode.val);
    visited.set(currentNode, clone);

    // Recursively clone all neighbors
    for (const neighbor of currentNode.neighbors) {
      clone.neighbors.push(dfs(neighbor));
    }

    return clone;
  }

  return dfs(node);
}

Here is how the algorithm works step by step:

• If the input node is null, return null immediately.
• Check the visited map. If the current node already has a clone, return that clone to break cycles.
• Otherwise, create a new Node with the same value and store it in the map before recursing. This ordering is critical — registering the clone first ensures that cyclic references resolve correctly.
• Iterate over each neighbor, recursively clone it, and append the cloned neighbor to the current clone's neighbors array.

Approach 2: BFS with a Queue

The BFS approach uses a queue to process nodes level by level. It is particularly useful when you want to avoid deep recursion stacks, which can cause stack overflow errors on very large graphs.

function cloneGraphBFS(node) {
  if (!node) return null;

  const visited = new Map();
  const queue = [node];

  // Clone the starting node and register it
  visited.set(node, new Node(node.val));

  while (queue.length > 0) {
    const current = queue.shift();

    for (const neighbor of current.neighbors) {
      if (!visited.has(neighbor)) {
        // Clone the neighbor and enqueue it for processing
        visited.set(neighbor, new Node(neighbor.val));
        queue.push(neighbor);
      }
      // Wire up the neighbor reference on the clone
      visited.get(current).neighbors.push(visited.get(neighbor));
    }
  }

  return visited.get(node);
}

The BFS algorithm proceeds as follows:

• Initialize the queue with the starting node and immediately create its clone in the map.
• While the queue is not empty, dequeue a node and iterate over its neighbors.
• For each unvisited neighbor, create a clone, store it in the map, and enqueue the original neighbor for later processing.
• Always push the cloned neighbor reference into the current clone's neighbors array, whether the neighbor was just created or already existed.

Testing the Implementation

To verify correctness, let us build a small graph, clone it, and confirm that the clone is structurally identical but referentially distinct from the original.

// Build a simple graph:
//   1 -- 2
//   |    |
//   4 -- 3

const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
const node4 = new Node(4);

node1.neighbors = [node2, node4];
node2.neighbors = [node1, node3];
node3.neighbors = [node2, node4];
node4.neighbors = [node1, node3];

// Clone the graph
const cloned = cloneGraphDFS(node1);

// Verify values match
console.log(cloned.val); // 1
console.log(cloned.neighbors[0].val); // 2
console.log(cloned.neighbors[1].val); // 4

// Verify it is a deep copy (different object references)
console.log(cloned === node1); // false
console.log(cloned.neighbors[0] === node2); // false

// Verify the cycle is preserved
console.log(cloned.neighbors[0].neighbors[0] === cloned); // true

The final assertion confirms that the cycle between node 1 and node 2 is correctly reconstructed in the cloned graph — the cloned node 2 points back to the cloned node 1, not the original.

Best Practices

When implementing graph cloning in JavaScript, keep the following best practices in mind:

• Always use a Map for visited tracking: A Map allows object keys, which is essential since graph nodes are objects. Plain objects with string keys will not work reliably for this purpose.
• Register clones before recursing: In DFS, store the clone in the map before processing neighbors. Otherwise, cyclic edges will trigger infinite recursion.
• Handle the empty graph case: Always check for a null or undefined input node at the start of your function.
• Prefer BFS for large graphs: Deep recursion can exceed the call stack limit. BFS with an explicit queue avoids this risk entirely.
• Consider edge cases: Test with a single node (no neighbors), disconnected components (if the problem allows them), and graphs with self-loops to ensure robustness.
• Avoid mutating the original graph: Your clone function should be a pure operation that never modifies the input. This guarantees the original graph remains intact for other consumers.

Time and Space Complexity

Both DFS and BFS solutions visit each node exactly once and traverse each edge twice (once from each endpoint). Therefore:

• Time complexity: O(V + E), where V is the number of vertices and E is the number of edges.
• Space complexity: O(V) for the visited map, plus O(V) for the recursion stack (DFS) or queue (BFS) in the worst case.

Conclusion

Cloning a graph in JavaScript is a fundamental skill that reinforces key concepts in graph traversal, reference management, and cycle detection. By leveraging a hash map to track visited nodes, both DFS and BFS approaches produce correct deep copies while avoiding infinite loops on cyclic structures. Whether you choose the elegance of recursive DFS or the stack safety of iterative BFS, the underlying principle remains the same: clone each node once, register it immediately, and wire up neighbor references using the map. Mastering this pattern not only prepares you for technical interviews but also equips you to handle complex data duplication tasks in real-world JavaScript applications.