深拷贝一个对象会了，怎么深拷贝一个图？

野性酷女 2022-11-06 06:54 151阅读 0赞

> 原创公众号：bigsai 如有帮助欢迎**一键三联**  
> 文章已收录在 [全网都在关注的数据结构与算法学习仓库][Link 1] 欢迎star

## 前言 ##

在前面，我写过一篇Java的深浅拷贝，那是基于对象的拷贝，但放眼数据结构与算法中，你有考虑过怎么拷贝一个图吗？(无向图)

在此之前，你需要对一些概念搞清楚：什么是深拷贝、浅拷贝？

**浅拷贝**：如果拷贝的是引用类型(非基本类型)，就只会拷贝一层(嵌套的对象不会被拷贝)，如果原对象发生改变，那么拷贝对象也会发生改变。

**深拷贝**：深拷贝的话会拷贝多层，嵌套的对象也会被拷贝出来，相当于开辟一个新的内存地址用于存放拷贝的对象。

用通俗一点(可能不完全确切)的话解释，浅拷贝就像你的双胞胎兄弟一样，你们父母亲人都是一样的；而深拷贝就像另一个平行的时空，那里有另一个你的一切。

既然搞懂了深浅拷贝以及其区别，我们再看看图，图一般用来表示节点和节点之间的关系，常分为有向图和无向图，在这里我们以无向图(一旦连接即双向)为主题。

我们对图的表示一般有邻接矩阵和邻接表，**邻接矩阵的话比较直观的表示一个图的连通性**，操作维护更简单，在Java中一般使用二维数组表示邻接矩阵，数组中的值可以表示两个节点的权值。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]  
使用邻接矩阵虽然简单但是有个比较差的就是**浪费较多内存空间**，所以很多情况还是使用**邻接表**来表示一个图，邻接表一般是数组+链表的这么一个组合。但是也有一些特殊情况各个节点比较独立的不用数组联立。

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

## 问题分析 ##

如果这个图使用邻接表表示，给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆），这个问题是[力扣131克隆图][131]原题。

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

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

![图片来源力扣][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 2]

给一个节点的引用，怎么克隆这个图呢？

如果只有这一个节点，那么克隆这个节点就好。如果这个节点只有一层邻居，那克隆这个邻居的列表(克隆List集合)即可。

但事实是这个节点可能有多层邻居，并且邻居之间可能存在着复杂联系。

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

克隆整个图，所以图的每一个节点都要被克隆的，我们需要使用图论的搜索算法来枚举所有节点，并且在**遍历的过程中我们需要想办法将节点之间的关系也克隆下来**。遍历的方法可以使用dfs或者bfs，这里使用bfs来实现。

凡是遇到苦难的时候我们模拟一下这个克隆的过程即可，通过下面这张图可以大概了解克隆图的过程中，最大的问题是要**避免创建重复节点**。即有的节点一旦被创建它的引用可能在后面会被用到的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 4]

那我们该如何解决这个问题呢？怎么样能够快速找到对应节点的引用？

这里最好的方法是使用`HashMap<Node,Node>`，其中key保存的是被克隆图中的节点，而value是在克隆图中所对应的节点，这样在克隆新图的过程中，我们遍历被克隆图中节点邻居的时候，就可以用哈希判断这个节点对应的value是否存在(即这个节点在克隆图中是否存在)。

*  如果存在那么直接使用`HashMap`找到对应节点放入克隆图中新创建的List中。
 *  不过不存在说明这个节点第一次遇到，克隆这个节点，先放到`hashMap`中与被克隆节点对应，然后放入克隆图中新创建的List中。

这个流程其中大概是这样的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 5]

有了上面的分析，想必你对这个问题的解决已经有了思路和想法，下面就提供一下代码实现。

/*
    // Definition for a Node.
    class Node {
        public int val;
        public List<Node> neighbors;
        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }
    */
    
    class Solution {
        
        public Node cloneGraph(Node node) {
        
            if(node==null)
    	    		return null;
    	    	Map<Node, Node>map=new HashMap<Node, Node>();//节点映射克隆的节点
    	    	
    	    	Queue<Node>oldqueue=new ArrayDeque<Node>();//bfs队列
    	    	oldqueue.add(node);
    	    	Node value=new Node(node.val);//先将返回的节点 创建、映射
    	    	map.put(node, value);
    	    	while (!oldqueue.isEmpty()) {
        
    				Node oldnode=oldqueue.poll();
    				Node newnode=map.get(oldnode);//找到这个节点对应克隆的映射(一定存在)
    				List<Node>list=oldnode.neighbors;//邻居
    				List<Node>listnew=new ArrayList<Node>();//克隆邻居
    				for(Node team:list)
    				{
        
    					if(map.containsKey(team))
    					{
        
    						listnew.add(map.get(team));
    						//点以前已经遇到，直接添加到邻居列表
    					}
    					else {
        //这个邻居第一次碰到，需要创建新节点赋予值
    						Node no=new Node(team.val);
    						map.put(team, no);//映射
    						listnew.add(no);
    						oldqueue.add(team);//这个点第一次遇到，要将它放到队列中进行bfs搜索
    					}
    				}
    				newnode.neighbors=listnew;//将节点的邻居指向list
    			}
    	    	return value;
        }
    }

本篇内容到这里就结束啦，还希望你能一键三联支持一下！  
新人求关注！关注后欢迎加入力扣打卡群(备注力扣 csdn即可)，持续产出肝货！

![image-20201114211553660][]

[Link 1]: https://github.com/javasmall/bigsai-algorithm
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]: /images/20221023/c8d7fdddd0f24185981530b8c9f0c2ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 1]: /images/20221023/5ad3241f389f4c4db8bc6a2301bf1d52.png
[131]: https://leetcode-cn.com/problems/clone-graph/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 2]: /images/20221023/2230ebcf6e7a453ebea02c66adf44dd4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 3]: /images/20221023/5eea944e06d44778a3c166aa0d393853.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 4]: /images/20221023/80f505f2e7dc49a8b86e0194fd2d5c27.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 5]: /images/20221023/b476b3821ad44c78bd75c0ce8b0674e9.png
[image-20201114211553660]: /images/20221023/79315d3aa42a47d78506ab5fd411e13e.png