137. Clone Graph

Leave a comment

September 4, 2016 by oneOokay

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.


这个和 copy list with random pointer其实是差不多的.两者的共同处都在于:

  • 要知道所有的节点
  • 要知道所有节点的neighbors
  • 新的list/graph里面的node都是新的

方法一:BFS:Queue遍历得到所有的点

方法二:DFS

方法一:BFS

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
 if (node == null) return node;
 Queue<UndirectedGraphNode> queue = new LinkedList<>(); //BFS
 HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
 map.put(node, new UndirectedGraphNode(node.label));
 queue.offer(node);
 while (!queue.isEmpty()){
 UndirectedGraphNode n = queue.poll();
 for (UndirectedGraphNode neighbor : n.neighbors){
 if (!map.containsKey(neighbor)){
 map.put(neighbor, new UndirectedGraphNode(neighbor.label));
 queue.offer(neighbor);
 }
 map.get(n).neighbors.add(map.get(neighbor));//加入的neighbor也应该是新的节点
 }
 }
 return map.get(node);
 }

方法二:DFS

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
 HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
 helper(node, map);
 return map.get(node);
 }
 
 private UndirectedGraphNode helper(UndirectedGraphNode node, HashMap<UndirectedGraphNode, UndirectedGraphNode> map){
 if (node == null) return node;
 if(map.containsKey(node)) return map.get(node);
 
 UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
 map.put(node, newNode);
 for (UndirectedGraphNode n : node.neighbors){
 newNode.neighbors.add(helper(n, map));
 }
 return map.get(node);
 }

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: