第一步加到map里面value是null只是为了去重，下一次遇到就不会进queue
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null){
return null;
}
Queue<UndirectedGraphNode> queue = new LinkedList<>();
Map<UndirectedGraphNode, UndirectedGraphNode> visited = new HashMap<>();
queue.offer(node);
visited.put(node, null);
while (!queue.isEmpty()){
UndirectedGraphNode curt = queue.poll();
UndirectedGraphNode copy = new UndirectedGraphNode(curt.label);
visited.put(curt, copy);
for (UndirectedGraphNode nei : curt.neighbors){
if (!visited.containsKey(nei)){
queue.offer(nei);
visited.put(nei, null);
}
}
}
for (UndirectedGraphNode orig : visited.keySet()){
UndirectedGraphNode copy = visited.get(orig);
for (UndirectedGraphNode nei : orig.neighbors){
copy.neighbors.add(visited.get(nei));
}
}
return visited.get(node);
}
}
