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.
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 private Dictionary<Node, Node> visited = new Dictionary<Node, Node>();
23
24 public Node CloneGraph(Node node) {
25 if (node == null) return null;
26 if (visited.ContainsKey(node))
27 return visited[node];
28
29 Node cloneNode = new Node(node.val, new List<Node>());
30 visited[node] = cloneNode;
31
32 foreach (Node neighbor in node.neighbors) {
33 cloneNode.neighbors.Add(CloneGraph(neighbor));
34 }
35
36 return cloneNode;
37 }
38}This C# code employs a Dictionary to handle deep copy operations for graph nodes. The recursive CloneGraph function ensures efficient cloning by storing already processed nodes in the visited map, thus making each node get processed only 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).
1from collections import deque
2
3class Node:
4 def __init__(self, val = 0, neighbors = None):
5 self.val = val
6 self.neighbors = neighbors if neighbors is not None else []
7
8class Solution:
9 def cloneGraph(self, node: 'Node') -> 'Node':
10 if not node:
11 return None
12
13 visited = {}
14 queue = deque([node])
15 visited[node] = Node(node.val, [])
16
17 while queue:
18 n = queue.popleft()
19 for neighbor in n.neighbors:
20 if neighbor not in visited:
21 visited[neighbor] = Node(neighbor.val, [])
22 queue.append(neighbor)
23 visited[n].neighbors.append(visited[neighbor])
24
25 return visited[node]The Python BFS implementation uses a deque for iterative traversal and a dictionary visited to record cloned nodes. It features level-wise cloning and linking of the nodes, ensuring all nodes are cloned and linked efficiently.