Q14: How do you Clone a Undirected Graph (Deep Copy with Cycles)?

Use a HashMap<Node, Node> to store mappings of (originalNode -> clonedNode) to handle cyclic references. Traverse graph using DFS or BFS: for each node, if not already cloned, create a new clone node, place in map, and recursively clone neighbor relationships.

DFS Graph Clone Solution

import java.util.*;

class Node {
    public int val;
    public List<Node> neighbors;
    public Node(int _val) { val = _val; neighbors = new ArrayList<>(); }
}

public class CloneGraph {
    private static final Map<Node, Node> visited = new HashMap<>();
    public static Node cloneGraph(Node node) {
        if (node == null) return null;
        if (visited.containsKey(node)) return visited.get(node);
        Node cloneNode = new Node(node.val);
        visited.put(node, cloneNode);
        for (Node neighbor : node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        return cloneNode;
    }
}

💡 Tracks visited nodes in a map to manage cyclic graph references during deep cloning.

Key Takeaways

HashMap tracks cloned copies to prevent infinite recursion on graph cycles.
DFS/BFS graph traversal produces identical deep-copied connectivity.

Knowledge Check

What issue arises if you attempt to deep copy a cyclic graph without maintaining a visited map?

Q14: How do you Clone a Undirected Graph (Deep Copy with Cycles)?

STAY UPDATED WITH BYTES!