Clone Graph: A Deep Copy Challenge

The "Clone Graph" problem is a classic challenge in computer science, focusing on the creation of a deep copy of a graph.

Problem Statement

Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a value (val) and a list (neighbors) of its neighbors.

Example

Consider a graph with nodes labeled 1, 2, 3, and 4, connected in the following structure:

• Node 1 is connected to nodes 2 and 4.
• Node 2 is connected to nodes 1 and 3.
• Node 3 is connected to nodes 2 and 4.
• Node 4 is connected to nodes 1 and 3.

A deep copy of this graph would be a new graph with the same structure but with different node instances.

Depth-First Search Solution

function cloneGraph(node: GraphNode) {
  if (!node) return null;
  const map = new Map();

  function dfs(node: GraphNode) {
    if (map.has(node)) return map.get(node);

    const clone = new GraphNode(node.val);
    map.set(node, clone);

    for (let neighbor of node.neighbors) {
      clone.neighbors.push(dfs(neighbor));
    }
    return clone;
  }

  return dfs(node);
}

Breaking Down the Solution

• Handle Empty Graph: Return null if the input graph is empty.
• Map for Cloned Nodes: Use a map to track cloned nodes to avoid duplications and handle cycles in the graph.
• Depth-First Search (DFS): Implement a DFS function to traverse the graph. For each node, create a clone and recursively clone its neighbors.
• Return Cloned Graph: Start DFS from the given node and return the cloned graph.

Conclusion

The Clone Graph problem exemplifies the application of depth-first search in graph theory and the intricacies of creating deep copies of complex structures. It's a valuable exercise for understanding graph traversal and the nuances of object references in programming.