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.

Examples#

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps us to check if you’re solving the correct problem:

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Try it yourself#

Implement your solution in clone_graph.py in the following coding playground. We have provided a useful code template in the other file that you may build on to solve this problem.