算法题 十 之 无向连接图的深度拷贝_无向图深度copy

题目

无向连接图的深度拷贝

图的表示方式，用数组表示与当前节点连接的节点，如下面的代码

class Node {
   public int val;
   public List<Node> neighbors;
}
1
2
3
4

思路

• 对于图片的拷贝，需要先掌握图的遍历，图的遍历可以使用深度与广度优先遍历。在这个题目里，我们采用深度优先遍历来解题。

深度优先遍历

• 递归调用各个节点。
• 遍历的出口？我们在遍历循环图的时候，是采用标志位当前节点是否已经遍历过了，如果遍历过了就不再遍历，避免重复以及死循环。
• 那么，我们是否可以也采用标志位的形式来避免死循环呢？答案是不行的。因为深度拷贝与遍历输出是不一样的。遍历输出只需要保证输出，而深度拷贝需要完整拷贝所有节点以及节点的结构。当设置标志位的形式会导致结构的不完全。
• 所以，我们采用缓存的形式来解决死循环的问题，定义一个哈希表，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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15