Clone Graph

这里使用BFS来解本题，BFS需要使用queue来保存neighbors

但这里有个问题，在clone一个节点时我们需要clone它的neighbors，而邻居节点有的已经存在，有的未存在，如何进行区分？

这里我们使用Map来进行区分，Map的key值为原来的node，value为新clone的node，当发现一个node未在map中时说明这个node还未被clone，

http://oj.leetcode.com/problems/clone-graph/

 1     public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
 2         if(node==null)
 3             return null;
 4         UndirectedGraphNode copyroot=new UndirectedGraphNode(node.label);
 5         UndirectedGraphNode copyfollow=copyroot;
 6         UndirectedGraphNode follow=node;
 7         
 8         Queue<UndirectedGraphNode> queue=new LinkedList();
 9         HashMap<UndirectedGraphNode,UndirectedGraphNode> copyHash=new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
10         queue.add(follow);
11         copyHash.put(follow, copyfollow);
12         while(queue.isEmpty()==false)
13         {
14             UndirectedGraphNode p=queue.poll();
15             copyfollow=copyHash.get(p);
16             if(p.neighbors!=null)
17                 copyfollow.neighbors=new ArrayList<UndirectedGraphNode>();
18             for(UndirectedGraphNode elem:p.neighbors)
19             {
20                 if(copyHash.containsKey(elem))
21                 {
22                     copyfollow.neighbors.add(copyHash.get(elem));
23                 }
24                 else
25                 {
26                     queue.add(elem);
27                     UndirectedGraphNode temp=new UndirectedGraphNode(elem.label);
28                     temp.neighbors=null;
29                     copyfollow.neighbors.add(temp);
30                     copyHash.put(elem, temp);
31                 }
32             }
33         }
34         return copyroot;
35     }

View Code