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.
1function Node(val, neighbors) {
2 this.val = val;
3 this.neighbors = neighbors ? neighbors : [];
4};
5
6var cloneGraph = function(node) {
7 let visited = new Map();
8
9 function dfs(node) {
10 if (!node) return node;
11 if (visited.has(node)) return visited.get(node);
12
13 let cloneNode = new Node(node.val);
14 visited.set(node, cloneNode);
15
16 node.neighbors.forEach(neighbor => {
17 cloneNode.neighbors.push(dfs(neighbor));
18 });
19
20 return cloneNode;
21 }
22
23 return dfs(node);
24};The JavaScript implementation uses a Map to keep track of visited nodes during the DFS traversal. The cloneGraph creates clones while traversing and uses stored clones for previously visited nodes, ensuring an acyclic processing.
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).
1using System;
2using System.Collections.Generic;
3
4public class Node {
5 public int val;
6 public IList<Node> neighbors;
7 public Node() {
8 val = 0;
9 neighbors = new List<Node>();
10 }
11 public Node(int _val) {
12 val = _val;
13 neighbors = new List<Node>();
14 }
15 public Node(int _val, List<Node> _neighbors) {
16 val = _val;
17 neighbors = _neighbors;
18 }
19}
20
21public class Solution {
22 public Node CloneGraph(Node node) {
23 if (node == null) return null;
24
25 Dictionary<Node, Node> visited = new Dictionary<Node, Node>();
26 Queue<Node> queue = new Queue<Node>();
27 queue.Enqueue(node);
28 visited[node] = new Node(node.val, new List<Node>());
29
30 while (queue.Count > 0) {
31 var n = queue.Dequeue();
32 foreach (var neighbor in n.neighbors) {
33 if (!visited.ContainsKey(neighbor)) {
34 visited[neighbor] = new Node(neighbor.val, new List<Node>());
35 queue.Enqueue(neighbor);
36 }
37 visited[n].neighbors.Add(visited[neighbor]);
38 }
39 }
40 return visited[node];
41 }
42}The C# solution employs a BFS approach with a queue, similar to other languages. A dictionary visited is used to track cloned nodes. The iterative nature ensures efficient node processing with level order traversal.