Problem
Given a reference to a node in a connected undirected graph, return a deep copy of the graph.Each node contains an integer value and a list of its neighboring nodes. The cloned graph must contain new nodes with the same values and connections as the original graph.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
adjList = [[2,4],[1,3],[2,4],[1,3]]
Graph
1 ----- 2
| |
| |
4 ----- 3
Output
1 ----- 2
| |
| |
4 ----- 3
Solution
This solution uses Depth-First Search (DFS) to traverse the graph and create a copy of each node.A HashMap is used to store the mapping between each original node and its cloned node. This ensures that every node is cloned only once and also prevents infinite recursion when the graph contains cycles.
For each node, we first check whether it has already been cloned. If so, the existing clone is returned. Otherwise, a new node is created and stored in the map before recursively cloning its neighbors.
Each cloned neighbor is then added to the neighbor list of the cloned node.
private Map<Node, Node> clones = new HashMap<>();
public Node cloneGraph(Node node) {
// Handle an empty graph.
if (node == null) {
return null;
}
// Return the existing clone.
if (clones.containsKey(node)) {
return clones.get(node);
}
// Create and store the clone.
Node clone = new Node(node.val);
clones.put(node, clone);
// Clone all neighbors.
for (Node neighbor : node.neighbors) {
clone.neighbors.add(cloneGraph(neighbor));
}
return clone;
}
Complexity
Each node is visited once, and every edge is processed once during traversal, resulting inO(V + E) time complexity.
The HashMap stores one cloned node for each original node, and the recursion stack can contain up to
V nodes.
BFS Approach
The graph can also be cloned using Breadth-First Search (BFS).We start by creating a clone of the given node and storing the original-to-clone mapping in a HashMap. A queue is then used to traverse the graph level by level.
For every neighbor, we check whether it has already been cloned. If not, a new clone is created, stored in the map, and the original neighbor is added to the queue for further processing.
The cloned neighbor is then added to the current cloned node's neighbor list.
public Node cloneGraph(Node node) {
// Handle an empty graph.
if (node == null) {
return null;
}
Map<Node, Node> clones = new HashMap<>();
Queue<Node> queue = new LinkedList<>();
// Create the first clone.
clones.put(node, new Node(node.val));
queue.offer(node);
while (!queue.isEmpty()) {
Node current = queue.poll();
// Process all neighbors.
for (Node neighbor : current.neighbors) {
if (!clones.containsKey(neighbor)) {
clones.put(neighbor, new Node(neighbor.val));
queue.offer(neighbor);
}
// Connect the cloned nodes.
clones.get(current).neighbors.add(clones.get(neighbor));
}
}
return clones.get(node);
}
Complexity
BFS visits every node and processes every edge, resulting inO(V + E) time complexity. The HashMap stores all cloned nodes, and the queue can contain up to V nodes.