原题链接在这里：https://leetcode.com/problems/clone-graph/
复制原来的graph, 输入是一个graph node, 返回也是一个 graph node.
可以利用BFS, 把当前点放进queue中，只要queue 不是空，每次从queue中poll()出来一个节点currentNode，然后把它的neighbors一次放入queue中。
这时如果它的neighbor已经遍历过了，就不应该再放进queue中防止infinite loop. 所以此时借助于HashMap hm.
键值对存储原graph的node, 和用原node.label复制出来的node. 检查这个neighbor是不是已经在hm的key中了，如果已经在了就跳过，如果没在就加到queue中，并建立一个自身的copy组成键值对放入hm中。
同时更新当前节点currentNode 复制点 的neighbors list. 此时无论它的neighbor是否在hm中都应该把hm中对应这个heighbor key 的 value 放到 list中。
最后返回 以输入点的label复制的点。
Note: Queue 是一个abstract class, 它不能用来直接initialize object, 还带用LinkedList, 所以下次可以直接用LinkedList, 不用Queue.
AC Java:
1 /** 2 * Definition for undirected graph. 3 * class UndirectedGraphNode { 4 * int label; 5 * List<UndirectedGraphNode> neighbors; 6 * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } 7 * }; 8 */ 9 public class Solution { 10 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { 11 if(node == null){ 12 return null; 13 } 14 Queue<UndirectedGraphNode> que = new LinkedList<UndirectedGraphNode>(); 15 HashMap<UndirectedGraphNode, UndirectedGraphNode> hm = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); 16 17 UndirectedGraphNode head = new UndirectedGraphNode(node.label); 18 hm.put(node, head); 19 que.offer(node); 20 21 while(!que.isEmpty()){ 22 UndirectedGraphNode currentNode = que.poll(); 23 for(UndirectedGraphNode neightborNode : currentNode.neighbors){ 24 if(!hm.containsKey(neightborNode)){ 25 que.offer(neightborNode); 26 hm.put(neightborNode, new UndirectedGraphNode(neightborNode.label)); 27 } 28 hm.get(currentNode).neighbors.add(hm.get(neightborNode)); 29 } 30 } 31 return head; 32 } 33 }
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/4865742.html