Useful Links for Explanation: 

这道题可以用BFS和DFS。DFS比较直观，但这里先说BFS。首先要审题，这道题给的constructor是个提示，就是new UndirectedGraphNode(int x){...}。这里面就是说你可以先用label去new一个UndirectedGraphNode，但是这个时候他的neighbors list是空的，以后你要在new出新的neighbor时，要把它加到这个list里面，完成全部copy。

所以这个题的做法是

1. 用一个HashMap去存新老node对应关系。

2. 用一个Queue来记录已经visit过的老node。

3. 从给定的node出发，每一次要把queue里面第一个node取出来，依次看这个node的neibor在hash里面有没有生成对应的新neighbor node。如果hash里面有这个neighbor node，就说明这个neighbor node对应的新neighbor node已经new过（但neigbor list可能是空的）。所以要把这个对应的新node拿出来，找到它的neighbor list。然后把这个老node的neigbor对应的新的neighbor node依次加进去。如果Hash里面没有这个neighbor node，还要加三部，第一步就是把这个未处理过的node加入到Queue里面。第二步new 这个新的neighor。第三步把这个加到Hash里。

/** * Definition for undirected graph. * class UndirectedGraphNode { *     int label; *     ArrayList
     
       neighbors; *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList
      
       (); } * }; */public class Solution {    /**     * @param node: A undirected graph node     * @return: A undirected graph node     */    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {        // write your code here        if (node == null) {            return null;        }                HashMap
       
         map = new HashMap<>();        Queue
        
          queue = new LinkedList<>();        UndirectedGraphNode head = new UndirectedGraphNode(node.label);        map.put(node, head);        queue.offer(node);        while (!queue.isEmpty()) {            UndirectedGraphNode curNode = queue.poll();            for (UndirectedGraphNode neighbor : curNode.neighbors) {                if (!map.containsKey(neighbor)) {                    queue.offer(neighbor);                    UndirectedGraphNode newNeighbor =                                        new UndirectedGraphNode(neighbor.label);                    map.put(neighbor, newNeighbor);                                    }                map.get(curNode).neighbors.add(map.get(neighbor));            }        }        return head;    }}