# [LintCode/LeetCode] Clone Graph [BFS/DFS]

## Problem

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

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

return a deep copied graph.

## Example

How we serialize an undirected graph.
Nodes are labeled uniquely.
As an example, consider the serialized graph `{0,1,2#1,2#2,2}`

## Note

``````public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
UndirectedGraphNode root = new UndirectedGraphNode(node.label);//複製根節點
Queue<UndirectedGraphNode> queue = new LinkedList<>();
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
queue.offer(node);//queue放入根結點
map.put(node, root);//map放入根結點和它的複製結點
while (!queue.isEmpty()) {
UndirectedGraphNode cur = queue.poll();//取出queue中（同一層）的結點進行BFS
for (UndirectedGraphNode n: cur.neighbors) {
//對沒有複製過的結點進行復制，並將這個結點放入queue
if (!map.containsKey(n)) {
map.put(n, new UndirectedGraphNode(n.label));
queue.offer(n);
}
//連線複製結點和複製neighbor結點
}
}
return root;
}
}``````

DFS

``````
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
return cloneNode(node, map);
}
private UndirectedGraphNode cloneNode(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
if (node == null) return node;
if (map.containsKey(node)) {
return map.get(node);
} else {
UndirectedGraphNode nodeCopy = new UndirectedGraphNode(node.label);
map.put(node, nodeCopy);
for (UndirectedGraphNode child : node.neighbors) {