Meta — Clone Graph (Deep Copy with DFS/BFS + HashMap)

Problem (Meta Graphs)

Given a reference to a node in a connected undirected graph, return a deep copy.

Node structure: val, neighbors: List[Node]

Solutions

Python — DFS

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

Python — BFS

from collections import deque

def cloneGraph(node):
    if not node: return None
    cloned = {node: Node(node.val)}
    q = deque([node])
    while q:
        cur = q.popleft()
        for nb in cur.neighbors:
            if nb not in cloned:
                cloned[nb] = Node(nb.val)
                q.append(nb)
            cloned[cur].neighbors.append(cloned[nb])
    return cloned[node]

JavaScript

function cloneGraph(node) {
    if (!node) return null;
    const map = new Map();
    const dfs = (n) => {
        if (map.has(n)) return map.get(n);
        const clone = {val:n.val,neighbors:[]};
        map.set(n, clone);
        for (const nb of n.neighbors) clone.neighbors.push(dfs(nb));
        return clone;
    };
    return dfs(node);
}

Java

import java.util.*;
Map<Node,Node> 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 nb:node.neighbors) clone.neighbors.add(cloneGraph(nb));
    return clone;
}

C++

#include <unordered_map>
using namespace std;
unordered_map<Node*,Node*> visited;
Node* cloneGraph(Node* node) {
    if(!node) return nullptr;
    if(visited.count(node)) return visited[node];
    Node* clone=new Node(node->val); visited[node]=clone;
    for(Node* nb:node->neighbors) clone->neighbors.push_back(cloneGraph(nb));
    return clone;
}

C

/* C: array-indexed clone map (node vals 1-100), DFS same pattern */