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

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.

Rust Solution

Rust's Rc<RefCell<Node>> carries the whole cost of a shared, mutable graph: Rc::clone only bumps the reference count (copying the pointer, not the node), while RefCell's borrow()/borrow_mut() push the borrow check to runtime. The memo is keyed by val as HashMap<i32, Rc<RefCell<Node>>>, whose value type must be spelled out explicitly, and a hit returns early via if let Some(c) = map.get(&val). Crucially, node.borrow().neighbors.clone() clones the neighbour Vec first so the immutable borrow ends before the recursive borrow_mut().neighbors.push(...), avoiding a double-borrow panic. The Option wrapper on input and output is unwrapped with match node { Some(n) => ..., None => None }.

Go Solution

Go keys the memo with map[int]*Node{} and probes it using the comma-ok form c, ok := visited[n.Val], the idiomatic presence check that returns the cached *Node on a hit. The recursion needs the two-step var dfs func(n *Node) *Node declaration before the closure is assigned, since a := closure cannot yet name itself. Neighbours accumulate through append(clone.Neighbors, dfs(nb)) on the nil slice left by &Node{Val: n.Val}, and the empty input is handled with a plain return nil rather than an Option. Because these are ordinary *Node pointers, Go's garbage collector spares it the reference-count and borrow ceremony the Rust version pays.