题目：
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
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 #.
0. Connect node 0 to both nodes 1 and 2.1. Connect node 1 to node 2.2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ / 0 --- 2
/ \_/
题目分析：
题目本身就是个图的遍历问题，其实只用看最上面的一句就OK了。下面整这么一篇就是为了说明Testcase，结果误导对了我好久。
其中注意的一点是，图中每一个点的权值是不一样的，所以可以采用取巧的方法检测这个点是否已经加在了图中，即使用HashMap
思路一：深度优先搜索
public static UndirectedGraphNode clone(UndirectedGraphNode node, HashMap<Integer, UndirectedGraphNode> nodeContainer) { if(nodeContainer.containsKey(node.label)){ return nodeContainer.get(node.label); } UndirectedGraphNode newNode=new UndirectedGraphNode(node.label); nodeContainer.put(newNode.label,newNode); for(int i =0;i<node.neighbors.size();i++){ newNode.neighbors.add(clone(node.neighbors.get(i),nodeContainer)); } return newNode; } public static UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if(node== null || node.equals(null)){ return null; } HashMap<Integer, UndirectedGraphNode> newNodeContainer = new HashMap<Integer, UndirectedGraphNode>(); return clone(node,newNodeContainer); }
思路二：广度优先搜索
XXX
原文：http://www.cnblogs.com/savageclc26/p/4884900.html