Solution: Clone Graph

Statement#

Given a graph that has nodes with data and a list of neighbors, create a deep copy of the graph. The graph has the following properties:

• Undirected: The edges of the graph are bidirectional.

• Connected: A path will always exist between any two nodes.

In a deep copy, a new instance of every node is created with the same data as in the original graph. Any modifications made to the new graph are not reflected in the original graph.

For simplicity, we are creating a graph using an adjacency list, where the data of each node is represented by its index in the adjacency list. Each list in the adjacency list describes the set of neighbors of a node in the graph. The index in the adjacency list starts from 1. For example, for [[2, 3], [1, 3], [1, 2]], there are three nodes in the graph:

$1^{st}$ node (data = 1): Neighbors are $2^{nd}$ node (data = 2) and $3^{rd}$ node (data = 3).

$2^{nd}$ node (data = 2): Neighbors are $1^{st}$ node (data = 1) and $3^{rd}$ node (data = 3).

$3^{rd}$ node (data = 3): Neighbors are $1^{st}$ node (data = 1) and $2^{nd}$ node (data = 2).

Constraints:

• $0 \leq$ Number of nodes $\leq 100$
• $1 \leq$ Node.data $\leq 100$
• Node.data is unique for each node.
• The graph is undirected, i.e., there are no self-loops or repeated edges.
• The graph is connected, i.e., any node can be visited from a given node.

Solution#

We use depth-first traversal and create a copy of each node while traversing the graph. We use a hash map to store each visited node to avoid getting stuck in cycles. We do not revisit nodes that exist in the hash map. The hash map key is a node in the original graph, and its value is the corresponding node in the cloned graph.

In order to solve this problem using the methodology discussed above, we create a recursive function, clone_helper, that takes two arguments: the current node being cloned and a hash map. The steps of this recursive function are given below:

1. If graph is empty, return NULL. This will also work as a base case for our recursive function.
2. If the current node is not NULL, create a new Node with the same data as the current node, and add the current node as key and its clone as value to the hash map.
3. Iterate through all the neighbors of the current node. For each neighbor, check if the neighbor is already cloned by looking up the neighbor in the hash map:
   • If the neighbor is not cloned yet, recursively call the function with the neighbor as the current node.
   • If the neighbor is already cloned, add the cloned neighbor to the new node’s neighbors.
4. Finally, return the new node.

The clone function is the main function that creates a deep copy of the graph. It takes a single argument, which is a reference to the root node of the graph. The function creates an empty hash map to keep track of nodes that have already been cloned. Then it calls the clone_helper function, passing in the root node and the hash map.

Time complexity#

The time complexity of this code is $O(n+m)$, where $n$ is the number of nodes, and $m$ is the number of edges.

Space complexity#

The space complexity of this code is $O(n)$, where $n$ is the number of nodes in the dictionary.

Note: We can also solve this problem using BFS.