Clone Graph — BFS/DFS with HashMap

Problem

Given a node of a connected undirected graph, return a deep copy (clone) of the graph.

Approach — DFS with visited map

Map original → clone. For each neighbour, if not cloned yet, recurse; then append clone to current node's neighbours.

Time: O(V+E) | Space: O(V)

Solutions

Python — DFS

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

Python — BFS

from collections import deque
class Solution:
    def cloneGraph(self, node):
        if not node: return None
        cloned={node: Node(node.val)}
        q=deque([node])
        while q:
            n=q.popleft()
            for nb in n.neighbors:
                if nb not in cloned:
                    cloned[nb]=Node(nb.val); q.append(nb)
                cloned[n].neighbors.append(cloned[nb])
        return cloned[node]

C++

class Solution {
    unordered_map<Node*,Node*> cloned;
    Node* dfs(Node* n){
        if(!n) return nullptr;
        if(cloned.count(n)) return cloned[n];
        cloned[n]=new Node(n->val);
        for(auto nb:n->neighbors) cloned[n]->neighbors.push_back(dfs(nb));
        return cloned[n];
    }
public:
    Node* cloneGraph(Node* n){ return dfs(n); }
};

Java

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

Complexity

Time: O(V+E) | Space: O(V)