Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.OJ's undirected graph serialization:Nodes are labeled uniquely.We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.As an example, consider the serialized graph {
    0,1,2#1,2#2,2}.The graph has a total of three nodes, and therefore contains three parts as separated by #.First node is labeled as 0. Connect node 0 to both nodes 1 and 2.Second node is labeled as 1. Connect node 1 to node 2.Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.Visually, the graph looks like the following:       1      / \     /   \    0 --- 2         / \         \_/

Leetcode里关于图的题其实并不多，这道题就是其中之一。DFS和BFS都可以做，遍历完原图的所有节点。这道题的难点在于neighbour关系的拷贝：原图中某一个点跟一些点具有neighbour关系，那么该点的拷贝也要与上述那些点的拷贝具有neighbour关系。那么，就需要很灵活地通过一个点访问该点的拷贝，最好的办法就是把该点与该点的拷贝存入一个HashMap。这样做还有一个好处，就是帮我们剩下了一个visited数组，我们可以用这个HashMap来知道哪些点我是访问过的。

方法是用BFS做的：

1 /** 2  * Definition for undirected graph. 3  * class UndirectedGraphNode { 4  *     int label; 5  *     List
     
       neighbors; 6  *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList
      
       (); } 7  * }; 8  */ 9 public class Solution {10     public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {11         if (node == null) return null;12         HashMap
       
         map = new HashMap
        
         ();13         LinkedList
         
           queue = new LinkedList
          
           ();14 queue.offer(node);15 UndirectedGraphNode copy = new UndirectedGraphNode(node.label);16 map.put(node, copy);17 while (!queue.isEmpty()) {18 UndirectedGraphNode cur = queue.poll();19 for (int i=0; i
          
         
        
       
      
     

网上看了别人的解法：

用Stack写的DFS方法：

1 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { 2     if(node == null) 3         return null; 4     LinkedList
     
       stack = new LinkedList
      
       (); 5     HashMap
       
         map = new HashMap
        
         (); 6     stack.push(node); 7     UndirectedGraphNode copy = new UndirectedGraphNode(node.label); 8     map.put(node,copy); 9     while(!stack.isEmpty())10     {11         UndirectedGraphNode cur = stack.pop();12         for(int i=0;i
        
       
      
     

用Recursion写的DFS方法：

1 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { 2     if(node == null) 3         return null; 4     HashMap
     
       map = new HashMap
      
       (); 5     UndirectedGraphNode copy = new UndirectedGraphNode(node.label); 6     map.put(node,copy); 7     helper(node,map); 8     return copy; 9 }10 private void helper(UndirectedGraphNode node, HashMap
       
         map)11 {12     for(int i=0;i