Clone an undirected graph.
Solution 1: BFS遍历图并复制点,再复制neighbors
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null){
return null;
}
Map<UndirectedGraphNode, UndirectedGraphNode> hashmap = new HashMap<>();
Queue<UndirectedGraphNode> queue = new LinkedList<>();
queue.offer(node);
UndirectedGraphNode node1 = new UndirectedGraphNode(node.label);
hashmap.put(node, node1);
while(!queue.isEmpty()){
UndirectedGraphNode newnode = queue.poll();
for(UndirectedGraphNode neighbour: newnode.neighbors){
if(hashmap.containsKey(neighbour)){
continue;
}
queue.offer(neighbour);
UndirectedGraphNode node2 = new UndirectedGraphNode(neighbour.label);
hashmap.put(neighbour, node2);
}
}
for(Map.Entry<UndirectedGraphNode, UndirectedGraphNode> entry : hashmap.entrySet()){
UndirectedGraphNode node3 = entry.getKey();
UndirectedGraphNode node4 = entry.getValue();
for(UndirectedGraphNode neighbour: node3.neighbors){
node4.neighbors.add(hashmap.get(neighbour));
}
}
return node1;
}
Solution 2: DFS
更好的DFS: