摘要：開始看這道題目的時候，沒有看懂和的作用。然后對這個放入的結(jié)點開始操作遍歷的所有，當前遍歷到的的叫做。當完成，則中沒有新的結(jié)點了，退出循環(huán)。返回在中更新過的，結(jié)束。

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.

How we serialize an undirected graph.
Nodes are labeled uniquely.
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
     / 
     \_/

開始看這道題目的時候，沒有看懂queue和hashmap的作用。
復制一個無向圖，先分析圖的結(jié)構(gòu)：label相當于圖結(jié)點的value，而neighbors相當于圖結(jié)點的所有next。然后考慮用什么方式復制：用queue用來標記當前正在復制的或已經(jīng)復制過的結(jié)點cur，而hashmap用來進行對新建無向圖結(jié)點root進行復制label和neighbors的操作。首先，從node結(jié)點開始，放入queue。然后對這個放入queue的結(jié)點cur開始操作：遍歷cur的所有neighbors，當前遍歷到的的neighbors叫做next。若map中不存在這個點，即沒有被復制過，就在map中復制這個結(jié)點next的label，同時存入queue以便在下次循環(huán)取出并復制其neighbors；無論map中包不包含這個neighbors結(jié)點next，都要將next加入map中對應(yīng)新建結(jié)點root的neighbors。當BFS完成，則queue中沒有新的結(jié)點了，退出while循環(huán)。返回在map中更新過的root，結(jié)束。
map.get(cur).neighbors.add(map.get(next));
這一句可以理解為，在for循環(huán)對cur的neighbors的遍歷中，先在HashMap里的root中建立新結(jié)點next，再將next放進root的結(jié)點cur的neighbors里。

// Definition for undirected graph.
class UndirectedGraphNode {
    int label;ArrayList neighbors;
    UndirectedGraphNode(int x) { 
        label = x; 
        neighbors = new ArrayList(); 
    }
}

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

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return node;

        Map map = new HashMap<>();
        map.put(node, new UndirectedGraphNode(node.label));                     //: <原結(jié)點, 復制結(jié)點>
        
        Queue queue = new LinkedList<>();
        queue.offer(node);                                                      //copy過的結(jié)點存入queue，以繼續(xù)遍歷其neighbor結(jié)點
        
        while (!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.poll();                             //取出copy過的結(jié)點，繼續(xù)復制其所有neighbor結(jié)點
            for (UndirectedGraphNode neighbor: cur.neighbors) {
                if (!map.containsKey(neighbor)) {                               //若結(jié)點未復制過，copy后存入queue
                    map.put(neighbor, new UndirectedGraphNode(neighbor.label));
                    queue.offer(neighbor);
                }
                map.get(cur).neighbors.add(map.get(neighbor));                  //將每個copied neighbor存入copied parent node
            }
        }
        return map.get(node);                                                   //返回copied根節(jié)點
    }
}

DFS

public class Solution {
   public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        Map map = new HashMap<>();
        return cloneNode(node, map);
    }
    private UndirectedGraphNode cloneNode(UndirectedGraphNode node, Map 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) {
                nodeCopy.neighbors.add(cloneNode(child, map));
            }
            return nodeCopy;
        }
    }
}