Clone an undirected graph. Each node in the graph contains
a label
and a list of
its neighbors
.
1 public class Solution { 2 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { 3 if(node==null) return node; 4 UndirectedGraphNode n1 = new UndirectedGraphNode(node.label); 5 HashMap<UndirectedGraphNode,UndirectedGraphNode> map = new HashMap<UndirectedGraphNode,UndirectedGraphNode>(); 6 map.put(node,n1); 7 LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>(); 8 queue.offer(node); 9 while(!queue.isEmpty()){ 10 UndirectedGraphNode original = queue.poll(); 11 ArrayList<UndirectedGraphNode> ons = original.neighbors; 12 for(int i=0;i<ons.size();i++){ 13 UndirectedGraphNode on = ons.get(i); 14 if(!map.containsKey(on)){ 15 queue.offer(on); 16 UndirectedGraphNode clone = new UndirectedGraphNode(on.label); 17 map.get(original).neighbors.add(clone); 18 map.put(on,clone); 19 } 20 else{ 21 map.get(original).neighbors.add(map.get(on)); 22 } 23 } 24 } 25 return n1; 26 } 27 }
原文:http://www.cnblogs.com/krunning/p/3563989.html