Clone Graph
Medium · Graphs · Explanation and code example
Breadth First Search
How it works
The graph can have cycles, so while cloning we must avoid creating duplicate nodes or looping forever.
Using Breadth First Search (BFS), we explore the graph level by level and keep a map from original nodes to their clones.
- When a node is first seen, create its clone and store it in the map.
- For every neighbor, ensure its clone exists, then connect the cloned nodes.
- The map guarantees each node is cloned only once.
Steps
- If the input node is
null, returnnull. - Create a map to store original node -> cloned node.
- Initialize a queue with the starting node and create its clone.
- While the queue is not empty:
- Pop a node.
- For each of its neighbors:
- If the neighbor is not cloned yet, clone it and add it to the queue.
- Add the cloned neighbor to the current node’s clone neighbor list.
- Return the cloned version of the starting node.
Complexity
- Time complexity:
O(V + E) - Space complexity:
O(V)
Where
Vis the number of vertices andEis the number of edges.
Things to watch for
Forgetting to Handle Cycles
Failing to track visited nodes causes infinite recursion when the graph contains cycles. Always use a map to store already-cloned nodes before processing neighbors.
Cloning the Same Node Multiple Times
Without a mapping from original to cloned nodes, the same node may be cloned multiple times, breaking the graph structure. Two neighbors pointing to the same original node should point to the same cloned node.
Adding Clone to Map After Processing Neighbors
The clone must be added to the map immediately after creation, before recursing on neighbors. Otherwise, back-edges to the current node will create a new clone instead of reusing the existing one.
Python code example
from typing import Optional
from collections import deque
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if not node:
return None
oldToNew = {}
oldToNew[node] = Node(node.val)
q = deque([node])
while q:
cur = q.popleft()
for nei in cur.neighbors:
if nei not in oldToNew:
oldToNew[nei] = Node(nei.val)
q.append(nei)
oldToNew[cur].neighbors.append(oldToNew[nei])
return oldToNew[node]
C++ code example
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
Node* cloneGraph(Node* node) {
if (!node) return nullptr;
unordered_map<Node*, Node*> oldToNew;
queue<Node*> q;
oldToNew[node] = new Node(node->val);
q.push(node);
while (!q.empty()) {
Node* cur = q.front();
q.pop();
for (Node* nei : cur->neighbors) {
if (oldToNew.find(nei) == oldToNew.end()) {
oldToNew[nei] = new Node(nei->val);
q.push(nei);
}
oldToNew[cur]->neighbors.push_back(oldToNew[nei]);
}
}
return oldToNew[node];
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.