# Question

Formatted question description: https://leetcode.ca/all/133.html

133	Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

1
/ \
/   \
0 --- 2
/ \
\_/

Note:
The number of nodes will be between 1 and 100.
The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.
Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
You must return the copy of the given node as a reference to the cloned graph.

@tag-graph


# Algorithm

In the recursive function, it is first to check if empty, and then to see whether the current node has been cloned,

• if it exists in the HashMap, it will directly return to its mapping node.
• Otherwise, clone the current node and create a mapping in HashMap, then traverse all neihbor nodes of the current node, call the recursive function and add it to the neighbors array of the cloned node.

Same idea of HashMap for BFS solution.

Java