Clone Graph

Given a reference of a node in a connected undirected graph.

Constraints:

• The number of nodes in the graph is in the range [0, 100].
• 1 <= Node.val <= 100
• Node.val is unique for each node.
• There are no repeated edges and no self-loops in the graph.
• The graph is connected and all nodes can be visited starting from the given node.

To create a clone, we must make sure a few things are correct.

• All nodes are reached, so that they can be cloned.
• All edges are correctly cloned between the correct nodes.

Therefore BFS seems to be the correct approach, as it will reach all nodes from the root, and will traverse using the edges.

def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
	if node is None:
		return None
	
	clones = {node: Node(node.val)}
	queue = [node]
	while queue:
		curr_node = queue.pop(0)
		for neighbour in curr_node.neighbors:
			if neighbour not in clones:
				clones[neighbour] = Node(neighbour.val)
				queue.append(neighbour)
			
			clones[curr_node].neighbors.append(clones[neighbour])
	
	return clones[node]

Time Complexity

We are only doing BFS here - so the algorithm takes $\mathcal{O}(V+ E)$ time.

Space Complexity

Since the output result isn’t considered as part of the space complexity analysis and no other variables are used, space is constant.