# 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. 1.
First node is labeled as`0`. Connect node`0`to both nodes`1`and`2`.
2. 2.
Second node is labeled as`1`. Connect node`1`to node`2`.
3. 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<>();
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) {