摘要：開始看這道題目的時(shí)候，沒有看懂和的作用。然后對(duì)這個(gè)放入的結(jié)點(diǎn)開始操作遍歷的所有，當(dāng)前遍歷到的的叫做。當(dāng)完成，則中沒有新的結(jié)點(diǎn)了，退出循環(huán)。返回在中更新過(guò)的，結(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
     / 
     \_/

開始看這道題目的時(shí)候，沒有看懂queue和hashmap的作用。
復(fù)制一個(gè)無(wú)向圖，先分析圖的結(jié)構(gòu)：label相當(dāng)于圖結(jié)點(diǎn)的value，而neighbors相當(dāng)于圖結(jié)點(diǎn)的所有next。然后考慮用什么方式復(fù)制：用queue用來(lái)標(biāo)記當(dāng)前正在復(fù)制的或已經(jīng)復(fù)制過(guò)的結(jié)點(diǎn)cur，而hashmap用來(lái)進(jìn)行對(duì)新建無(wú)向圖結(jié)點(diǎn)root進(jìn)行復(fù)制label和neighbors的操作。首先，從node結(jié)點(diǎn)開始，放入queue。然后對(duì)這個(gè)放入queue的結(jié)點(diǎn)cur開始操作：遍歷cur的所有neighbors，當(dāng)前遍歷到的的neighbors叫做next。若map中不存在這個(gè)點(diǎn)，即沒有被復(fù)制過(guò)，就在map中復(fù)制這個(gè)結(jié)點(diǎn)next的label，同時(shí)存入queue以便在下次循環(huán)取出并復(fù)制其neighbors；無(wú)論map中包不包含這個(gè)neighbors結(jié)點(diǎn)next，都要將next加入map中對(duì)應(yīng)新建結(jié)點(diǎn)root的neighbors。當(dāng)BFS完成，則queue中沒有新的結(jié)點(diǎn)了，退出while循環(huán)。返回在map中更新過(guò)的root，結(jié)束。
map.get(cur).neighbors.add(map.get(next));
這一句可以理解為，在for循環(huán)對(duì)cur的neighbors的遍歷中，先在HashMap里的root中建立新結(jié)點(diǎn)next，再將next放進(jìn)root的結(jié)點(diǎn)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);//復(fù)制根節(jié)點(diǎn)
        Queue queue = new LinkedList<>();
        Map map = new HashMap<>();
        queue.offer(node);//queue放入根結(jié)點(diǎn)
        map.put(node, root);//map放入根結(jié)點(diǎn)和它的復(fù)制結(jié)點(diǎn)
        while (!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.poll();//取出queue中（同一層）的結(jié)點(diǎn)進(jìn)行BFS
            for (UndirectedGraphNode n: cur.neighbors) {
                //對(duì)沒有復(fù)制過(guò)的結(jié)點(diǎn)進(jìn)行復(fù)制，并將這個(gè)結(jié)點(diǎn)放入queue
                if (!map.containsKey(n)) {
                    map.put(n, new UndirectedGraphNode(n.label));
                    queue.offer(n);
                }
                //連接復(fù)制結(jié)點(diǎn)和復(fù)制neighbor結(jié)點(diǎn)
                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é)點(diǎn), 復(fù)制結(jié)點(diǎn)>
        
        Queue queue = new LinkedList<>();
        queue.offer(node);                                                      //copy過(guò)的結(jié)點(diǎn)存入queue，以繼續(xù)遍歷其neighbor結(jié)點(diǎn)
        
        while (!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.poll();                             //取出copy過(guò)的結(jié)點(diǎn)，繼續(xù)復(fù)制其所有neighbor結(jié)點(diǎn)
            for (UndirectedGraphNode neighbor: cur.neighbors) {
                if (!map.containsKey(neighbor)) {                               //若結(jié)點(diǎn)未復(fù)制過(guò)，copy后存入queue
                    map.put(neighbor, new UndirectedGraphNode(neighbor.label));
                    queue.offer(neighbor);
                }
                map.get(cur).neighbors.add(map.get(neighbor));                  //將每個(gè)copied neighbor存入copied parent node
            }
        }
        return map.get(node);                                                   //返回copied根節(jié)點(diǎn)
    }
}

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;
        }
    }
}