深拷贝一个图的方法教程，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。
前言
在此之前，你需要对一些概念搞清楚：什么是深拷贝、浅拷贝?
浅拷贝：如果拷贝的是引用类型(非基本类型)，就只会拷贝一层(嵌套的对象不会被拷贝)，如果原对象发生改变，那么拷贝对象也会发生改变。
深拷贝：深拷贝的话会拷贝多层，嵌套的对象也会被拷贝出来，相当于开辟一个新的内存地址用于存放拷贝的对象。
用通俗一点(可能不完全确切)的话解释，浅拷贝就像你的双胞胎兄弟一样，你们父母亲人都是一样的;而深拷贝就像另一个平行的时空，那里有另一个你的一切。
既然搞懂了深浅拷贝以及其区别，我们再看看图，图一般用来表示节点和节点之间的关系，常分为有向图和无向图，在这里我们以无向图(一旦连接即双向)为主题。
我们对图的表示一般有邻接矩阵和邻接表，邻接矩阵的话比较直观的表示一个图的连通性，操作维护更简单，在Java中一般使用二维数组表示邻接矩阵，数组中的值可以表示两个节点的权值。
邻接矩阵表示一个图
使用邻接矩阵虽然简单但是有个比较差的就是浪费较多内存空间，所以很多情况还是使用邻接表来表示一个图，邻接表一般是数组+链表的这么一个组合。但是也有一些特殊情况各个节点比较独立的不用数组联立。
邻接表表示一个图
问题分析
如果这个图使用邻接表表示，给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝(克隆)，这个问题是力扣131克隆图原题。
图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。
class Node { public int val; public List<Node> neighbors; }
图片来源力扣
给一个节点的引用，怎么克隆这个图呢?
如果只有这一个节点，那么克隆这个节点就好。如果这个节点只有一层邻居，那克隆这个邻居的列表(克隆List集合)即可。
但事实是这个节点可能有多层邻居，并且邻居之间可能存在着复杂联系。
可能的一个图
克隆整个图，所以图的每一个节点都要被克隆的，我们需要使用图论的搜索算法来枚举所有节点，并且在遍历的过程中我们需要想办法将节点之间的关系也克隆下来。遍历的方法可以使用dfs或者bfs，这里使用bfs来实现。
凡是遇到苦难的时候我们模拟一下这个克隆的过程即可，通过下面这张图可以大概了解克隆图的过程中，最大的问题是要避免创建重复节点。即有的节点一旦被创建它的引用可能在后面会被用到的。
模拟克隆的过程
那我们该如何解决这个问题呢?怎么样能够快速找到对应节点的引用?
这里最好的方法是使用HashMap，其中key保存的是被克隆图中的节点，而value是在克隆图中所对应的节点，这样在克隆新图的过程中，我们遍历被克隆图中节点邻居的时候，就可以用哈希判断这个节点对应的value是否存在(即这个节点在克隆图中是否存在)。
如果存在那么直接使用HashMap找到对应节点放入克隆图中新创建的List中。
不过不存在说明这个节点第一次遇到，克隆这个节点，先放到hashMap中与被克隆节点对应，然后放入克隆图中新创建的List中。
这个流程其中大概是这样的：
其中一个过程Map的变化和作用
有了上面的分析，想必你对这个问题的解决已经有了思路和想法，下面就提供一下代码实现。
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; } }看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注编程网行业资讯频道，感谢您对编程网的支持。
