DIY: Clone Undirected 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 list.

Each node in the graph contains a data (int) and a list (List[Node]) of its neighbors.

class Node {
  public int data;
  public List<Node> neighbors = new ArrayList<Node>();
}

Input

The input graph will be in the form of an adjacency list. 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 list. The following is an example output:

G` = {{2,4},{1,3},{2,4},{1,3}}

Coding exercise

Implement the clone(rootNode) function, where rootNode 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.