Clone an undirected graph. Each node in the graph contains a?label
?and a list of its?neighbors
.
[解題思路]
圖的遍歷有兩種方式,BFS和DFS
這里使用BFS來解本題,BFS需要使用queue來保存neighbors
LEETCODE。但這里有個問題,在clone一個節點時我們需要clone它的neighbors,而鄰居節點有的已經存在,有的未存在,如何進行區分?
這里我們使用Map來進行區分,Map的key值為原來的node,value為新clone的node,當發現一個node未在map中時說明這個node還未被clone,
將它clone后放入queue中處理neighbors。
使用Map的主要意義在于充當BFS中Visited數組,它也可以去環問題,例如A--B有條邊,當處理完A的鄰居node,然后處理B節點鄰居node時發現A已經處理過了
處理就結束,不會出現死循環!
leetcode 5,queue中放置的節點都是未處理neighbors的節點!!!!
1 /** 2 * Definition for undirected graph. 3 * class UndirectedGraphNode { 4 * int label; 5 * ArrayList<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 // Note: The Solution object is instantiated only once and is reused by each test case. 12 if(node == null){ 13 return node; 14 } 15 UndirectedGraphNode result = new UndirectedGraphNode(node.label); 16 LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>(); 17 queue.add(node); 18 Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); 19 map.put(node, result); 20 21 while(!queue.isEmpty()){ 22 UndirectedGraphNode nodeInQueue = queue.poll(); 23 ArrayList<UndirectedGraphNode> neighbors = nodeInQueue.neighbors; 24 for(int i = 0; i < neighbors.size(); i++){ 25 UndirectedGraphNode n1 = neighbors.get(i); 26 if(map.containsKey(n1)){ 27 map.get(nodeInQueue).neighbors.add(map.get(n1)); 28 } else { 29 UndirectedGraphNode n1clone = new UndirectedGraphNode(n1.label); 30 map.get(nodeInQueue).neighbors.add(n1clone); 31 map.put(n1, n1clone); 32 queue.add(n1); 33 } 34 } 35 36 } 37 return result; 38 } 39 }
?ref:
http://leetcode.com/2012/05/clone-graph-part-i.html