DSA
Clone Graph
Graphs problem — solution with code and analysis.
Practice Here
Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph.
BFS with Hash Map#
The challenge in cloning a graph is that nodes can be referenced from multiple neighbours — we must create each clone exactly once and then wire up the edges correctly. BFS is a natural fit because it visits every reachable node in breadth-first order; as each node is dequeued, we iterate over its neighbours, creating a clone for any neighbour we haven't seen before (tracked via an old → new hash map) and then linking the current clone's neighbors list to the already-created (or just-created) neighbour clone. This runs in O(N + E) time and O(N) auxiliary space for the queue and map, which is optimal since every node and edge must be visited at least once.
- Use a map to store new old node to new node mapping
- While traversing(BFS), creating the new graph too.
/*
// 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) {
//old node - new node mapping
unordered_map<Node*, Node*> mp;
if(!node)
return NULL;
Node* first = new Node(node->val, {});
mp[node] = first;
queue<Node*> q;
q.push(node);
while(!q.empty())
{
Node* curr = q.front();
q.pop();
for(auto next: curr->neighbors)
{
if(mp.find(next) == mp.end())
{
mp[next] = new Node(next->val, {});
q.push(next);
}
mp[curr]->neighbors.push_back(mp[next]);
}
}
return mp[node];
}
};