DIY: Clone Directed Graph

Problem statement

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. The graph is represented using an adjacency array.

Each node in the graph contains a data (int) and an array (Array[Node]) of its neighbors.

class Node {
    data = None
    neighbors = []
}

Input

The input graph will be in the form of an adjacency array. The following is an example input:

G = [[2,4],[1,3],[2,4],[1,3]]

Output

The output will be a deep copy of the input graph, and it will be in the form of an adjacency array. The following is an example output:

G` = [[2,4],[1,3],[2,4],[1,3]]

Coding exercise

Implement the clone(root) function, where root is the input’s graph starting node through which the rest of the graph can be traversed. The function returns the root node of the cloned graph.