本题考察的是图搜索
题目描述
克隆一张无向图，图中的每个节点包含一个 label （标签）和一个 neighbors （邻接点）列表 。
OJ的无向图序列化：
节点被唯一标记。
我们用 # 作为每个节点的分隔符，用 , 作为节点标签和邻接点的分隔符。
例如，序列化无向图 {0,1,2#1,2#2,2}。
该图总共有三个节点, 被两个分隔符 # 分为三部分。
第一个节点的标签为 0，存在从节点 0 到节点 1 和节点 2 的两条边。
第二个节点的标签为 1，存在从节点 1 到节点 2 的一条边。
第三个节点的标签为 2，存在从节点 2 到节点 2 (本身) 的一条边，从而形成自环。
我们将图形可视化如下：
image.png
题目思考
首先应该对图进行遍历，使用深度优先搜索或者广度优先搜索都可以，在遍历的过程中不断克隆结点。使用HashMap来保存已克隆的结点。
代码
使用队列
public class Solution {
//BFS
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node==null)
return null;
Map<Integer,UndirectedGraphNode> map=new HashMap<Integer,UndirectedGraphNode>();//保存已克隆的结点
Queue<UndirectedGraphNode> queue1=new LinkedList<UndirectedGraphNode>();//使用队列继续宁深度优先搜索
queue1.offer(node);
UndirectedGraphNode head=new UndirectedGraphNode(node.label);
map.put(head.label,head);
while(!queue1.isEmpty()){
UndirectedGraphNode temp =queue1.poll();
List<UndirectedGraphNode> temp_list = temp.neighbors;
for(int i=0;i<temp_list.size();i++){//为该节点添加相邻结点
UndirectedGraphNode temp_neighbor =temp_list.get(i);
UndirectedGraphNode new_node=map.get(temp_neighbor.label);
if(new_node==null){//如果还没有创建该相邻结点，创建并添加到map中
new_node=new UndirectedGraphNode(temp_neighbor.label);
map.put(temp_neighbor.label,new_node);
queue1.offer(temp_neighbor);
}
map.get(temp.label).neighbors.add(new_node);
}
}
return head;
}
}
使用递归
