Neetcode - Clone Graph
Code like someone will read it tomorrow — because they will (and it might be you).
Clone Graph
Given a node in a connected undirected graph, return a deep copy of the graph.
Each node in the graph contains an integer value and a list of its neighbors.
The graph is shown in the test cases as an adjacency list. An adjacency list is a mapping of nodes to lists, used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
For simplicity, nodes values are numbered from 1 to n, where n is the total number of nodes in the graph. The index of each node within the adjacency list is the same as the node's value (1-indexed).
The input node will always be the first node in the graph and have 1 as the value.
Input: adjList = [[2],[1,3],[2]]
Output: [[2],[1,3],[2]]
Explanation: There are 3 nodes in the graph.
Node 1: val = 1 and neighbors = [2].
Node 2: val = 2 and neighbors = [1, 3].
Node 3: val = 3 and neighbors = [2].
Input: adjList = [[]]
Output: [[]]
Explanation: The graph is empty.
We previously studied graph problems in the Neetcode - Number of Islands. Today, we explore how a graph can be constructed from a given set of relationships. Even though the input in this case represents the same graph structure, it still demonstrates that a graph can be built from any structured relationship.
This highlights the power of graphs in capturing patterns within data. Once a graph is constructed, it opens the door to numerous potential insights and discoveries based on its structure.
In this problem, we're given the first node with a value of 1, and nodes are numbered up to n (1-indexed). To clone the graph, we need some form of memoization to avoid revisiting nodes — which helps prevent infinite cycles during traversal. The corresponding code is shown below.
class Solution {
unordered_map<Node*, Node*> visited;
public:
Node* cloneGraph(Node* node) {
if (!node) return nullptr;
if (visited.find(node) != visited.end()) {
return visited[node];
}
Node* clone = new Node(node->val);
visited[node] = clone;
for (auto neighbor : node->neighbors) {
clone->neighbors.push_back(cloneGraph(neighbor));
}
return clone;
}
};
DFS - CSY
Let's see how BFS approach works as well.
class Solution {
public:
Node *cloneGraph(Node *node) {
if (!node)
return nullptr;
std::unordered_map<Node *, Node *> visited;
std::queue<Node *> q;
visited[node] = new Node(node->val);
q.push(node);
while (!q.empty()) {
Node *current = q.front();
q.pop();
for (auto neighbor : current->neighbors) {
if (visited.find(neighbor) == visited.end()) {
visited[neighbor] = new Node(neighbor->val);
q.push(neighbor);
}
visited[current]->neighbors.push_back(visited[neighbor]);
}
}
return visited[node];
}
}BFS - CSY
his approach is quite similar to the DFS-based solution. The main difference lies in the use of a queue structure for BFS traversal. We start by pushing the first node into the queue. Then, for each node we dequeue, we iterate through its neighbors. If a neighbor hasn’t been visited yet (i.e., it's not in the map), we create a new node for it, store it in the map, and push it into the queue to explore its neighbors later.
One part that might seem a bit unusual is that we return visited[node] at the end. But think of it simply as returning the entry point of the newly cloned graph. Once you see it from that perspective, it makes perfect sense.
Conclusion
We learned how to construct a graph from a given structure, such as an adjacency list or neighbor relationships. Once we understand how to recursively traverse and copy its neighbors, it becomes clear that a graph can be built from any dataset that defines pairwise or structured relationships. This shows how powerful graphs are as a data structure — they can represent complex systems and unlock deep insights through algorithms once the structure is properly built.
