# Clone Graph

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 `#`.

1. First node is labeled as `0`. Connect node `0` to both nodes `1` and `2`.
2. Second node is labeled as `1`. Connect node `1` to node `2`.
3. 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
/ \
\_/
```

Solution: BFS遍历图 用Hash表存储Original Node-》 Copy Node 映射
O(n) time complexity, O(n) space

```public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
queue.offer(node);
UndirectedGraphNode copyRoot = new UndirectedGraphNode(node.label);
map.put(node, copyRoot);
while (!queue.isEmpty()) {
int count = queue.size();
for (int i = 0; i < count; i++) {
UndirectedGraphNode curr = queue.poll();
for (UndirectedGraphNode neighbor : curr.neighbors) {
if (!map.containsKey(neighbor)) {
queue.offer(neighbor);
UndirectedGraphNode currCopy = new UndirectedGraphNode(neighbor.label);
map.put(neighbor, currCopy);
}
}
}
}
for (UndirectedGraphNode originalNode : map.keySet()) {
for (UndirectedGraphNode neighbor : originalNode.neighbors) {