# 133 Clone Graph

## 1. Question

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
/ \
\_/``````

## 2. Implementation

(1) BFS

``````/**
* Definition for undirected graph.
* class UndirectedGraphNode {
*     int label;
*     List<UndirectedGraphNode> neighbors;
*     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}

Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
Queue<UndirectedGraphNode> queue = new LinkedList<>();

map.put(node, new UndirectedGraphNode(node.label));

while (!queue.isEmpty()) {
UndirectedGraphNode curNode = queue.remove();

for (UndirectedGraphNode nextNode : curNode.neighbors) {
if (!map.containsKey(nextNode)) {
map.put(nextNode, new UndirectedGraphNode(nextNode.label));
}
}
}
return map.get(node);
}
}``````

(2) DFS

``````public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();

return dfs(node, map);
}

public UndirectedGraphNode dfs(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
if (node == null) {
return null;
}

if (map.containsKey(node)) {
return map.get(node);
}

UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
map.put(node, copy);

for (UndirectedGraphNode neighbor : node.neighbors) {