题目链接
思路：
采用广度优先搜索来对图进行深拷贝。
由于是无向图，那么为了避免从A遍历到B，再从B遍历到A的这种情况发生，需要对遍历过的节点进行标记，这里我们使用Map进行标记即可。
使用一个队列来存放节点，使用一个Map来存放每一个节点（key），这个节点的拷贝（value），这个Map也可以用于判断节点是否已经访问过。
对于队列中的每一个节点，弹出时，若之前没有访问过它的邻居，那么将这个节点的邻居作为key，重新拷贝一个这个节点作为value，放入到Map中。并且将这个节点的邻居加入到队列中。对于当前节点，更新它的拷贝的邻居list。
此题就是遍历图中的每一个节点，对每一个节点都进行拷贝，并对每一个节点的邻居也进行拷贝的过程。
public Node cloneGraph(Node node) {if (node == null) {return node;}// 存放遍历过的节点Map<Node, Node> visited = new HashMap<>();// 将当前node节点以及它的拷贝加入到map中visited.put(node, new Node(node.val, new ArrayList<>()));Queue<Node> queue = new LinkedList<>();queue.add(node);while (!queue.isEmpty()) {// 当前节点弹出Node cur = queue.poll();// 遍历当前节点的邻居，进行拷贝for (Node neighbor : cur.neighbors) {// 之前没有访问过，需要进行拷贝if (!visited.containsKey(neighbor)) {visited.put(neighbor, new Node(neighbor.val, new ArrayList<>()));queue.add(neighbor);}// 拿到当前节点的拷贝节点，对其邻居list进行更新visited.get(cur).neighbors.add(visited.get(neighbor));}}return node;}class Node {public int val;public List<Node> neighbors;public Node() {val = 0;neighbors = new ArrayList<Node>();}public Node(int _val) {val = _val;neighbors = new ArrayList<Node>();}public Node(int _val, ArrayList<Node> _neighbors) {val = _val;neighbors = _neighbors;}}