Clone Graph

Problem Statement

You’re a graph architect tasked with duplicating an undirected graph. Given a node, return a deep copy with identical structure and values. This medium-level DFS/BFS challenge is a replication riddle—map nodes to avoid cycles!

Example

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]

Graph:

1---2
|   |
|   |
4---3

Output: A new graph with same structure

Input: adjList = [[]]

Output: Single node copy

Input: adjList = []

Output: null

Code

class Solution {
    private Map map = new HashMap<>();
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (map.containsKey(node)) return map.get(node);
        Node clone = new Node(node.val);
        map.put(node, clone);
        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneGraph(neighbor));
        }
        return clone;
    }
}
            

class Solution:
    def cloneGraph(self, node):
        if not node:
            return None
        cloned = {}
        def dfs(node):
            if node in cloned:
                return cloned[node]
            clone = Node(node.val)
            cloned[node] = clone
            for neighbor in node.neighbors:
                clone.neighbors.append(dfs(neighbor))
            return clone
        return dfs(node)
            

function cloneGraph(node) {
    if (!node) return null;
    let cloned = new Map();
    function dfs(node) {
        if (cloned.has(node)) return cloned.get(node);
        let clone = new Node(node.val);
        cloned.set(node, clone);
        for (let neighbor of node.neighbors) {
            clone.neighbors.push(dfs(neighbor));
        }
        return clone;
    }
    return dfs(node);
}
            

Explanation

• DFS Insight: Map tracks cloned nodes to handle cycles; recurse to build neighbors.
• Flow: Clone node, map it, recursively clone neighbors, link them.
• Example Walkthrough: 1→2→4 → clone 1, 2, 4, link back to 1—map prevents re-cloning.
• BFS Alt: Queue-based, level-by-level cloning—same result.
• Key Detail: Hash map ensures O(1) lookup for cycle detection.

Note