【Leetcode】133.克隆图

133 克隆图

题目

给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

class Node {
    public int val;
    public List<Node> neighbors;
}

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

方法一（DFS）

深拷贝一个图的意思为：要重新构建一张新的图，其中所有的节点都需要new出来，图的值和结构都和原图一样。

根据给定的这个节点，可以通过深度优先遍历走遍图中的所有节点。每到一个节点，先判断其是否访问过。

  • 若这个节点已经访问过，则直接返回它的拷贝节点。
  • 若这个节点还未访问过，就根据这个节点new出一个新的拷贝节点。先给这个新节点赋值，再填充它的邻接列表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    //map的key为原图中的节点，value为根据它拷贝出的新节点
    Map<Node, Node> map = new HashMap<>();
    //此递归函数会返回node的深拷贝节点
    public Node cloneGraph(Node node) {
        //递归结束条件
        if(node == null)
            return null;
        //若这个节点已经访问过，则直接返回它的拷贝节点。
        if(map.containsKey(node))
            return map.get(node);
        //若这个节点还未访问过，就根据这个节点构造一个新的拷贝节点
        Node newNode = new Node(node.val);
        //这时已经访问完了节点node，因此要更新map
        map.put(node, newNode);
        //根据node的邻接列表，填充新节点newNode的邻接列表
        for(Node neighbor: node.neighbors){
            newNode.neighbors.add(cloneGraph(neighbor));
        }
        return newNode;
    }
}
  • 时间复杂度：O(N) 每个节点只会被访问一次
  • 空间复杂度：O(N) 哈希表需要O(N)的空间，递归使用的栈深度需要O(H)的空间（H为图的深度）。总空间复杂度为O(N)

方法二（BFS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public Node cloneGraph(Node node) {
        if(node == null)
            return null;
        //map的key为原图中的节点，value为根据它拷贝出的新节点
        Map<Node, Node> map = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        //先将node节点入队列
        queue.add(node);
        map.put(node, new Node(node.val));
        //通过BFS遍历到所有节点，在遍历的过程中更新map
        while(!queue.isEmpty()){
            Node temp = queue.poll();
            for(Node neighbor: temp.neighbors){
                //如果此节点未被遍历过，一方面正常的走BFS的流程，将其入队列
                //另一方面构造它的拷贝节点，填充拷贝节点的值，并更新map
                if(!map.containsKey(neighbor)){
                    map.put(neighbor, new Node(neighbor.val));
                    queue.add(neighbor);
                }
                //填充该节点neighbor对应的拷贝节点neighbor'的邻接列表
                //在邻接链表中加入temp'和neighbor'的邻接关系
                map.get(neighbor).neighbors.add(map.get(temp));
            }
        }
        //至此，所有新节点的值和邻接列表都已填充好，可以返回。
        return map.get(node);
    }
}
  • 时间复杂度：O(N) 每个节点只会被访问一次
  • 空间复杂度：O(N) 哈希表需要O(N)的空间，BFS所用的队列最多需要O(N)的空间，总空间复杂度为O(N)