[Leetcode][第133题][JAVA][克隆图][DFS][BFS][深拷贝]

淩亂°似流年 2022-11-27 15:40 113阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

#### 【解答思路】 ####

其实就是深拷贝的一个实现，深拷贝就是对于所有的指针成员，不能仅仅是赋值，还有重新分配空间。

深拷贝反应在本题中就是，所有的结点需要重新new出来，而不是直接赋值。  
整体的思路依然是dfs，跑遍原图中每个结点，然后根据原结点生成新结点。  
要注意的地方就是，因为图存在环，所以要标记访问过的结点，避免重复形成死循环：  
如果该结点已经被访问过，则不再遍历该结点，而是直接将指针值赋给自己邻接点数组----浅拷贝；  
如果该结点没有被访问过，则继续dfs遍历该结点，并将产生的新结点----深拷贝；

###### 1. DFS ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]

**时间复杂度：O(N) 空间复杂度：O(N)**  
![在这里插入图片描述][20200816010031567.png_pic_center]

class Solution { 
    // 哈希表对应关系，节点1 --> 节点1的克隆
        private HashMap <Node, Node> visited = new HashMap <> ();
        public Node cloneGraph(Node node) { 
            if (node == null) { 
                return node;
            }
    
            // 如果该节点已经被访问过了，则直接从哈希表中取出对应的克隆节点返回
            if (visited.containsKey(node)) { 
                return visited.get(node);
            }
    
            // 克隆节点，注意到为了深拷贝我们不会克隆它的邻居的列表
            Node cloneNode = new Node(node.val, new ArrayList());
            // 哈希表存储
            visited.put(node, cloneNode);
    
            // 遍历该节点的邻居并更新克隆节点的邻居列表
            for (Node neighbor: node.neighbors) { 
                cloneNode.neighbors.add(cloneGraph(neighbor));
            }
            return cloneNode;
        }
    }

###### 2. BFS ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]

**时间复杂度：O(N) 空间复杂度：O(N)**  
![在这里插入图片描述][20200816010245133.png_pic_center]

class Solution { 
        public Node cloneGraph(Node node) { 
            if (node == null) { 
                return node;
            }
    
            HashMap<Node, Node> visited = new HashMap();
    
            // 将题目给定的节点添加到队列
            LinkedList<Node> queue = new LinkedList<Node> ();
            queue.add(node);
            // 克隆第一个节点并存储到哈希表中
            visited.put(node, new Node(node.val, new ArrayList()));
    
            // 广度优先搜索
            while (!queue.isEmpty()) { 
                // 取出队列的头节点
                Node n = queue.remove();
                // 遍历该节点的邻居
                for (Node neighbor: n.neighbors) { 
                    if (!visited.containsKey(neighbor)) { 
                        // 如果没有被访问过，就克隆并存储在哈希表中
                        visited.put(neighbor, new Node(neighbor.val, new ArrayList()));
                        // 将邻居节点加入队列中
                        queue.add(neighbor);
                    }
                    // 更新当前节点的邻居列表
    				// record.get(n)表示通过原节点得到它的克隆节点
                    // 继续.neighbors.add(record.get(neighbor))表示往它的克隆节点中加入邻接节点
                    // 为什么是add(record.get(neighbor))而不是add(neighbor)
                    // 因为n是原图的节点，record.get(neighbor)才是我们在上面if里克隆出的新节点
    
    
                    visited.get(n).neighbors.add(visited.get(neighbor));
                }
            }
    
            return visited.get(node);
        }
    }

#### 【总结】 ####

###### 1. 课本上总说deep copy和shallow copy，似懂非懂的，不觉得这东西有什么用。慢慢地，发现deep copy背后隐藏的逻辑其实是一种对象图（Object Graph）的遍历行为——这东西广泛出现在各语言的垃圾回收、序列化机制里。内存里各个对象存储空间中放置的引用域/指针就好像有向图里一条边，你沿着它去到达内存中的每个角落、去到当前对象所有的关联对象。题设里的neibours就像一道开胃菜，它可以是其他collection、甚至object，学会这个deep copy，你也就学会了GC里的可达性分析、你也就学会了如何把RAM中的数据固化到硬盘里。 ######

###### 2.读题困难 对HashMap的读取操作不熟悉导致理解困难 ######

转载链接：https://leetcode-cn.com/problems/clone-graph/solution/ke-long-tu-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/4c18b437523e423fb7f20db651cbc6e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/a7806d846d204d1b95d894a677dd9c99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/6d5606166a094e30943a2a2205e54edb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/1eabaf42cac2474aa5b3df346541b2ae.png
[20200816010031567.png_pic_center]: /images/20221124/4cbde0ee7f264e5491e7e208b25df035.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221124/2a4ae0729f424740ab028b8d25295ff2.png
[20200816010245133.png_pic_center]: /images/20221124/123c6920260d41e3bf3a930f4fbafb7a.png