# 133. Clone Graph

## Approach 1: BFS

• Time: $O(|V| + |E|)$
• Space: $O(|V| + |E|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public: Node* cloneGraph(Node* node) { if (node == nullptr) return nullptr; queue q{{node}}; unordered_map map{{node, new Node(node->val)}}; while (!q.empty()) { Node* u = q.front(); q.pop(); for (Node* v : u->neighbors) { if (!map.count(v)) { map[v] = new Node(v->val); q.push(v); } map[u]->neighbors.push_back(map[v]); } } return map[node]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public Node cloneGraph(Node node) { if (node == null) return null; Queue q = new ArrayDeque<>(Arrays.asList(node)); Map map = new HashMap<>(); map.put(node, new Node(node.val)); while (!q.isEmpty()) { Node u = q.poll(); for (Node v : u.neighbors) { if (!map.containsKey(v)) { map.put(v, new Node(v.val)); q.offer(v); } map.get(u).neighbors.add(map.get(v)); } } return map.get(node); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def cloneGraph(self, node: 'Node') -> 'Node': if not node: return None q = collections.deque([node]) map = {node: Node(node.val)} while q: u = q.popleft() for v in u.neighbors: if v not in map: map[v] = Node(v.val) q.append(v) map[u].neighbors.append(map[v]) return map[node] 

## Approach 2: DFS

• Time: $O(|V| + |E|)$
• Space: $O(|V| + |E|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public: Node* cloneGraph(Node* node) { if (node == nullptr) return nullptr; if (const auto it = map.find(node); it != map.cend()) return it->second; Node* newNode = new Node(node->val); map[node] = newNode; for (Node* neighbor : node->neighbors) newNode->neighbors.push_back(cloneGraph(neighbor)); return newNode; } private: unordered_map map; }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public Node cloneGraph(Node node) { if (node == null) return null; if (map.containsKey(node)) return map.get(node); Node newNode = new Node(node.val); map.put(node, newNode); for (Node neighbor : node.neighbors) newNode.neighbors.add(cloneGraph(neighbor)); return newNode; } private Map map = new HashMap<>(); } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution: def cloneGraph(self, node: 'Node') -> 'Node': if not node: return None if node in self.map: return self.map[node] newNode = Node(node.val, []) self.map[node] = newNode for neighbor in node.neighbors: self.map[node].neighbors.append(self.cloneGraph(neighbor)) return newNode map = {}