题目
无向连接图的深度拷贝
图的表示方式,用数组表示与当前节点连接的节点,如下面的代码
class Node {
public int val;
public List<Node> neighbors;
}
思路
- 对于图片的拷贝,需要先掌握图的遍历,图的遍历可以使用深度与广度优先遍历。在这个题目里,我们采用深度优先遍历来解题。
深度优先遍历
- 递归调用各个节点。
- 遍历的出口?我们在遍历循环图的时候,是采用标志位当前节点是否已经遍历过了,如果遍历过了就不再遍历,避免重复以及死循环。
- 那么,我们是否可以也采用标志位的形式来避免死循环呢?答案是不行的。因为深度拷贝与遍历输出是不一样的。遍历输出只需要保证输出,而深度拷贝需要完整拷贝所有节点以及节点的结构。当设置标志位的形式会导致结构的不完全。
- 所以,我们采用缓存的形式来解决死循环的问题,定义一个哈希表,Key为旧节点,value为新节点。当递归调用时,先判断缓存里是否有新节点,如果没有在创建节点,当创建完新节点后,要在遍历下一个节点前把新节点放入缓存。
附上代码
Map<Node,Node> cache = new HashMap<>();
public Node cloneGraph(Node node) {
if(cache.get(node) != null){
return cache.get(node);
}
Node newNode = new Node();
cache.put(node,newNode);// 调用新节点前,放入缓存
newNode.val = node.val;
List<Node> neighbors = node.neighbors;
for (Node tempNode : neighbors) {
newNode.neighbors.add(cloneGraph(tempNode));
}
return newNode;
}