Given a reference to a node in a connected undirected graph, return a deep copy of the entire graph. Each node has an integer value and a list of its neighbors. The graph can have between 0 and 100 nodes with unique values from 1 to 100. There are no self-loops or repeated edges.
Example
Graph: 1 -- 2 -- 3 -- 1 (a triangle where 1 connects to 2 and 3, and 2 connects to 3)
Output: A new graph with the same structure – node 1’ connects to 2’ and 3’, node 2’ connects to 1’ and 3’, node 3’ connects to 1’ and 2’. All nodes are new objects, not references to the originals.
Use BFS or DFS with a hashmap that maps each original node to its clone. When you visit a node, create its clone and store it in the map. Then for each neighbor, either retrieve the existing clone or create a new one, and connect them.
Why this works
You need to create a copy of every node and replicate every edge, without getting stuck in cycles. The hashmap serves two purposes: it tracks which nodes have already been cloned (preventing infinite loops), and it lets you look up any node’s clone in O(1) when wiring up neighbor connections.
Step by step
- Clone the start node — create a copy and store the original-to-clone mapping in a hashmap.
- BFS through the original graph — for each node you dequeue, iterate over its neighbors.
- Clone unseen neighbors — if a neighbor is not in the hashmap yet, clone it and enqueue it for processing.
- Wire up edges — for every neighbor (whether newly cloned or previously seen), add the cloned neighbor to the cloned current node’s neighbor list.
Time: O(V+E)
Space: O(V)
class Node {
public int val;
public List<Node> neighbors;
public Node(int val) {
this.val = val;
this.neighbors = new ArrayList<>();
}
}
class Solution {
public Node cloneGraph(Node node) {
if (node == null) {
return null;
}
Map<Node, Node> clones = new HashMap<>();
clones.put(node, new Node(node.val)); // map original → clone
Queue<Node> queue = new LinkedList<>();
queue.offer(node);
while (!queue.isEmpty()) {
Node current = queue.poll();
for (Node neighbor : current.neighbors) {
if (!clones.containsKey(neighbor)) {
clones.put(neighbor, new Node(neighbor.val)); // clone neighbor on first encounter
queue.offer(neighbor);
}
clones.get(current).neighbors.add(clones.get(neighbor)); // link cloned nodes
}
}
return clones.get(node);
}
}
class Node {
public:
int val;
vector<Node*> neighbors;
Node(int val) : val(val) {}
};
class Solution {
public:
Node* cloneGraph(Node* node) {
if (!node) {
return nullptr;
}
unordered_map<Node*, Node*> clones;
clones[node] = new Node(node->val); // map original → clone
queue<Node*> q;
q.push(node);
while (!q.empty()) {
Node* current = q.front();
q.pop();
for (Node* neighbor : current->neighbors) {
if (!clones.count(neighbor)) {
clones[neighbor] = new Node(neighbor->val); // clone neighbor on first encounter
q.push(neighbor);
}
clones[current]->neighbors.push_back(clones[neighbor]); // link cloned nodes
}
}
return clones[node];
}
};
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def cloneGraph(node: 'Node | None') -> 'Node | None':
if not node:
return None
clones = {node: Node(node.val)} # map original → clone
queue = deque([node])
while queue:
current = queue.popleft()
for neighbor in current.neighbors:
if neighbor not in clones:
clones[neighbor] = Node(neighbor.val) # clone neighbor on first encounter
queue.append(neighbor)
clones[current].neighbors.append(clones[neighbor]) # link cloned nodes together
return clones[node]