Nodes are labeled uniquely.

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 #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. 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         /          \_/



对于图的遍历，无非是深度优先和广度优先。在这里采用的是广度优先搜索。
题目的关键点在于完全克隆，也就是说遇到的每一个节点必须复制一份出来，另外如果有连通的边（指针），也需要复制一份出来。
采用HashMap将原节点与克隆节点进行对应可以实现。在遍历到节点X时，也得到X‘,对X的所有相邻节点进行讨论，如果是新相邻节点（HashMap中不存在）N，则复制一份N‘，复制点N‘与X‘相连，并把对应的二者（N,N‘）放入HashMap中，新相邻节点（N）入队列。
如果发现节点N已遍历过，则只需要把它复制点N‘与当前遍历点的复制点X‘连接，即为复制一条边。

代码：

 1 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { 2         if(node==null) 3             return null; 4         Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>(); 5         HashMap<UndirectedGraphNode, UndirectedGraphNode> hm = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); 6          7         q.add(node); 8         UndirectedGraphNode copy = new UndirectedGraphNode(node.label); 9         hm.put(node, copy);10         while(!q.isEmpty())11         {12             UndirectedGraphNode temp = q.poll();13             UndirectedGraphNode tempCopy = hm.get(temp);14             List<UndirectedGraphNode> N = temp.neighbors;15             for(int i=0;i<N.size();i++) {16                 UndirectedGraphNode tempN = N.get(i);17                 if(!hm.containsKey(tempN)) {18                     UndirectedGraphNode copyN = new UndirectedGraphNode(tempN.label);19                     tempCopy.neighbors.add(copyN);20                     hm.put(tempN, copyN);21                     q.add(tempN);22                 }23                 else {24                     tempCopy.neighbors.add(hm.get(tempN));25                 }26             }27         }28         return copy;29     }

Copy List with Random Pointer:

 1 public RandomListNode copyRandomList(RandomListNode head) { 2         if(head==null) 3             return null; 4         Queue<RandomListNode> q = new LinkedList<RandomListNode>(); 5         q.add(head); 6         HashMap<RandomListNode,RandomListNode> hm = new HashMap<RandomListNode,RandomListNode>(); 7         RandomListNode headCopy = new RandomListNode(head.label); 8         hm.put(head,headCopy); 9         while(!q.isEmpty())10         {11             RandomListNode temp = q.poll();12             RandomListNode copyTemp = hm.get(temp);13             RandomListNode nTemp = temp.next;14             RandomListNode rTemp = temp.random;15             if(nTemp!=null)16             {17                 if(!hm.containsKey(nTemp)) {18                     RandomListNode copyNext = new RandomListNode(nTemp.label);19                     copyTemp.next = copyNext;20                     hm.put(nTemp,copyNext);21                     q.add(nTemp);22                 }23                 else24                     copyTemp.next = hm.get(nTemp);25             }26             if(rTemp!=null)27             {28                 if(!hm.containsKey(rTemp)) {29                     RandomListNode copyRandom = new RandomListNode(rTemp.label);30                     copyTemp.random = copyRandom;31                     hm.put(rTemp,copyRandom);32                     q.add(rTemp);33                 }34                 else35                     copyTemp.random = hm.get(rTemp);36             }37         }38         return headCopy;39     }