转载请联系bigsai公众号。前言里写了Java的深浅拷贝，就是基于对象的拷贝，但是看数据结构和算法，有没有考虑过怎么拷贝一个图？（无向图）在此之前，你需要明确一些概念：什么是深拷贝和浅拷贝？浅拷贝：如果拷贝是引用类型（非基本类型），只会拷贝一层（不会拷贝嵌套对象），如果原对象发生变化，那么拷贝的对象也会发生变化。深拷贝：深拷贝会拷贝多层，嵌套的对象也会拷贝出来，相当于开辟了一个新的内存地址用于存放拷贝的对象。用更通俗（可能不完全准确）的话来解释，浅拷贝就像你的孪生兄弟，你的父母和亲人一样；而深拷贝就像另一个平行时空，那里有另一个你。了解了深拷贝和浅拷贝及其区别之后，我们再来看一下图。图一般用来表示节点之间的关系，常分为有向图和无向图。这里我们使用无向图（一旦连接即双向）作为主题。我们一般用邻接矩阵和邻接表来表示图。邻接矩阵更直观的表示图的连通性，运维更简单。在Java中，一般用二维数组来表示邻接矩阵。数组中的值可以代表两个节点的权重。邻接矩阵表示一个图。使用邻接矩阵虽然简单，但是浪费了更多的内存空间。因此，在很多情况下，邻接表被用来表示一个图。邻接表一般就是这样一个数组和链表的组合。但也有一些特殊情况，每个节点都是相对独立的，不需要用数组来组合。图问题分析的邻接表表示如果此图由邻接表表示，并且给你一个无向连通图中节点的引用，请返回该图的深拷贝（克隆）。这个问题就是131克隆图的原问题。图中的每个节点都包含它的值val(int)和它的邻居列表(list[Node])。classNode{publicintval;publicListneighbors;}图像的来源是对节点的引用。如何克隆这个图？如果只有这个节点，那么克隆这个节点即可。如果该节点只有一层邻居，则只需克隆邻居列表（克隆List集合）。但事实是这个节点可能有多层邻居，邻居之间可能有复杂的联系。图有可能克隆整个图，因此必须克隆图的每个节点。我们需要利用图论的搜索算法来枚举所有的节点，在遍历过程中需要想办法找到节点之间的关系。也是克隆出来的。遍历方式可以使用dfs或者bfs，这里使用bfs。每当我们遇到困难时，我们都可以模拟克隆过程。通过下图，我们可以大致了解克隆图的过程。最大的问题是避免创建重复节点。也就是说，一旦创建了一些节点，它们的引用可能会在以后使用。模拟克隆过程，那么我们如何解决这个问题呢？怎样才能快速找到对应节点的引用呢？这里最好的方式是使用HashMap，key存放的是克隆图中的节点，value是克隆图中的节点。这样，在克隆新图的过程中，当我们遍历节点的邻居时对于克隆图，我们可以通过哈希来判断该节点对应的值是否存在（即该节点是否存在于克隆图中）。如果存在，则直接使用HashMap找到对应的节点，放入克隆图中新建的List中。但是不存在，说明第一次遇到这个节点，clone这个节点，先把它放到被克隆节点对应的hashMap中，然后再放到clonemap中新建的List中。这个过程大致是这样的：其中一个进程Map的变化和作用，经过上面的分析，想必你对解决这个问题有了思路和思路，下面给出代码实现。/*//DefinitionforaNode.classNode{publicintval;publicListneighbors;publicNode(){val=0;neighbors=newArrayList();}publicNode(int_val){val=_val;neighbors=newArrayList();}publicNode(int_val,ArrayList_neighbors){val=_val;neighbors=_neighbors;}}*/classSolution{publicNodecloneGraph(Nodenode){if(node==null)returnnull;Mapmap=newHashMap();//节点映射克隆节点Queueoldqueue=newArrayDeque();//bfs队列oldqueue.add(node);Nodevalue=newNode(node.val);//首先创建并映射返回的节点map.put(node,value);while(!oldqueue.isEmpty()){Nodeoldnode=oldqueue.poll();Nodenewnode=map.get(oldnode);//找到这个节点的映射对应clone（必须存在）Listlist=oldnode.neighbors;//NeighborsListlistnew=newArrayList();//Cloneneighborsfor(Nodeteam:list){if(map.containsKey(team)){listnew.add(map.get(team));//之前遇到过的点，直接加入邻居列表}else{//这个邻居是enc第一次失败，需要创建一个新节点并赋值Nodeno=newNode(team.val);map.put(team,no);//maplistnew.add(no);oldqueue。add(team);//这个点是第一次遇到，放入队列中供bfs搜索}}newnode.neighbors=listnew;//将节点的邻居指向列表}returnvalue;}}结论到此为止，本篇内容到此结束，后面会继续分享一些优秀而巧妙的问题和算法，对本篇进行总结。如果有帮助，请点个赞，观看分享一波！
