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.
1class Node:
2 def __init__(self, val = 0, neighbors = None):
3 self.val = val
4 self.neighbors = neighbors if neighbors is not None else []
5
6class Solution:
7 def __init__(self):
8 self.visited = {}
9
10 def cloneGraph(self, node: 'Node') -> 'Node':
11 if not node:
12 return None
13
14 if node in self.visited:
15 return self.visited[node]
16
17 clone_node = Node(node.val, [])
18 self.visited[node] = clone_node
19
20 if node.neighbors:
21 clone_node.neighbors = [self.cloneGraph(n) for n in node.neighbors]
22
23 return clone_nodeThis Python implementation uses a dictionary visited to map original nodes to their clones. The cloneGraph function recursively creates and returns deep copies by processing neighbors recursively.
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).
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 public Node cloneGraph(Node node) {
22 if (node == null) return null;
23
24 Map<Node, Node> visited = new HashMap<>();
25 Queue<Node> queue = new LinkedList<>();
26 queue.add(node);
27 visited.put(node, new Node(node.val, new ArrayList<>()));
28
29 while (!queue.isEmpty()) {
30 Node n = queue.poll();
31 for (Node neighbor : n.neighbors) {
32 if (!visited.containsKey(neighbor)) {
33 visited.put(neighbor, new Node(neighbor.val, new ArrayList<>()));
34 queue.add(neighbor);
35 }
36 visited.get(n).neighbors.add(visited.get(neighbor));
37 }
38 }
39 return visited.get(node);
40 }
41}This Java BFS solution involves using a queue to iteratively process and clone nodes level by level. The map visited ensures each node is cloned exactly once, and relationships are established as nodes are dequeued and processed.