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.
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Node {
6public:
7 int val;
8 vector<Node*> neighbors;
9 Node() {
10 val = 0;
11 neighbors = vector<Node*>();
12 }
13 Node(int _val) {
14 val = _val;
15 neighbors = vector<Node*>();
16 }
17 Node(int _val, vector<Node*> _neighbors) {
18 val = _val;
19 neighbors = _neighbors;
20 }
21};
22
23class Solution {
24public:
25 unordered_map<Node*, Node*> visited;
26
27 Node* cloneGraph(Node* node) {
28 if (!node) return NULL;
29 if (visited.find(node) != visited.end())
30 return visited[node];
31
32 Node* cloneNode = new Node(node->val);
33 visited[node] = cloneNode;
34
35 for (auto neighbor : node->neighbors) {
36 cloneNode->neighbors.push_back(cloneGraph(neighbor));
37 }
38 return cloneNode;
39 }
40};This C++ solution utilizes a class Node and a class Solution. The cloneGraph function checks if a node is already cloned via the visited map, ensures deep copying by recursively cloning neighbors, and returns the deep clone of the input node.
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).
1function Node(val, neighbors) {
2 this.val = val;
3 this.neighbors = neighbors ? neighbors : [];
4};
5
6var cloneGraph = function(node) {
7 if (!node) return null;
8 const visited = new Map();
9 const queue = [node];
10 visited.set(node, new Node(node.val));
11
12 while (queue.length) {
13 const n = queue.shift();
14 for (const neighbor of n.neighbors) {
15 if (!visited.has(neighbor)) {
16 visited.set(neighbor, new Node(neighbor.val));
17 queue.push(neighbor);
18 }
19 visited.get(n).neighbors.push(visited.get(neighbor));
20 }
21 }
22 return visited.get(node);
23};The JavaScript solution for graph cloning uses a queue for BFS traversal, maintaining a map to record cloned nodes. Level-wise cloning and linking are handled within the while loop. This guarantees efficient processing and avoids deep recursion.