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 #.
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
/ \
\_/
需要对原图进行BFS搜索，其中Set<UndirectedGraphNode> visited对已经访问过的节点进行记录，Map<UndirectedGraphNode, UndirectedGraphNode> map用来记录新老节点的对应关系。代码实现如下：
1 import java.util.HashMap;
2 import java.util.HashSet;
3 import java.util.LinkedList;
4 import java.util.Map;
5 import java.util.Queue;
6 import java.util.Set;
7
8 public class CloneGraph {
9 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
10 if (node == null)
11 return node;
12 Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
13 queue.add(node);
14 Set<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
15 Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
16 while (!queue.isEmpty()) {
17 UndirectedGraphNode n = queue.remove();
18 if (visited.contains(n))
19 continue;
20 visited.add(n);
21 UndirectedGraphNode clone;
22 if (!map.containsKey(n)) {
23 clone = new UndirectedGraphNode(n.label);
24 map.put(n, clone);
25 } else {
26 clone = map.get(n);
27 }
28 for (UndirectedGraphNode child : n.neighbors) {
29 queue.add(child);
30 UndirectedGraphNode cloneChild;
31 if (!map.containsKey(child)) {
32 cloneChild = new UndirectedGraphNode(child.label);
33 map.put(child, cloneChild);
34 } else {
35 cloneChild = map.get(child);
36 }
37 clone.neighbors.add(cloneChild);
38 }
39 }
40 return map.get(node);
41 }
42 }