The Depth-First Search (DFS) approach is one of the most intuitive ways to solve the graph cloning problem. Here, we will recursively explore each node starting from the root (Node 1) and keep a map to store already cloned nodes, ensuring each node is cloned once.
For each node, we:
Time Complexity: O(V+E), where V is the number of vertices and E is the number of edges. This is because we visit each node and edge once.
Space Complexity: O(V), for the recursion stack and the clone map.
1import java.util.*;
2
3class Node {
4 public int val;
5 public List<Node> neighbors;
6 public Node() {
7 val = 0;
8 neighbors = new ArrayList<Node>();
9 }
10 public Node(int _val) {
11 val = _val;
12 neighbors = new ArrayList<Node>();
13 }
14 public Node(int _val, ArrayList<Node> _neighbors) {
15 val = _val;
16 neighbors = _neighbors;
17 }
18}
19
20class Solution {
21 private Map<Node, Node> visited = new HashMap<>();
22
23 public Node cloneGraph(Node node) {
24 if (node == null) return null;
25
26 if (visited.containsKey(node)) {
27 return visited.get(node);
28 }
29
30 Node cloneNode = new Node(node.val, new ArrayList<>());
31 visited.put(node, cloneNode);
32
33 for (Node neighbor : node.neighbors) {
34 cloneNode.neighbors.add(cloneGraph(neighbor));
35 }
36 return cloneNode;
37 }
38}The Java solution involves using a HashMap to track visited nodes. cloneGraph recursively clones each node and its neighbors if not already cloned, ensuring that each node is processed once.
An alternative approach is to use Breadth-First Search (BFS), which is iterative in nature. Here, we utilize a queue to help explore each node level by level, preventing deep recursion and managing each node's clone in a breadth-wise manner.
In this BFS approach:
Time Complexity: O(V+E).
Space Complexity: O(V).
1#include <vector>
2#include <unordered_map>
3#include <queue>
4using namespace std;
5
6class Node {
7public:
8 int val;
9 vector<Node*> neighbors;
10 Node() {
11 val = 0;
12 neighbors = vector<Node*>();
13 }
14 Node(int _val) {
15 val = _val;
16 neighbors = vector<Node*>();
17 }
18 Node(int _val, vector<Node*> _neighbors) {
19 val = _val;
20 neighbors = _neighbors;
21 }
22};
23
24class Solution {
25public:
26 Node* cloneGraph(Node* node) {
27 if (!node) return NULL;
28 unordered_map<Node*, Node*> visited;
29 queue<Node*> q;
30 q.push(node);
31 visited[node] = new Node(node->val);
32
33 while (!q.empty()) {
34 auto n = q.front(); q.pop();
35 for (auto neighbor : n->neighbors) {
36 if (visited.find(neighbor) == visited.end()) {
37 visited[neighbor] = new Node(neighbor->val);
38 q.push(neighbor);
39 }
40 visited[n]->neighbors.push_back(visited[neighbor]);
41 }
42 }
43 return visited[node];
44 }
45};This C++ BFS-based solution utilizes a queue to explore nodes level by level. We maintain a map visited to keep track of the original to clone node mapping. Each node and its neighbors are iteratively visited, cloned, and linked.