刚学会深拷贝一个对象，学妹却问我怎么深拷贝一个图

本文转载自微信公众号「bigsai」，作者bigsai。转载本文请联系bigsai公众号。

前言

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

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

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

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

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

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

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

邻接矩阵表示一个图

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

邻接表表示一个图

问题分析

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

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

 
 
 
 
    
  
  
  
  
  1. class Node {
    2. 
  
  
  
  
  2.     public int val;
    3. 
  
  
  
  
  3.     public List neighbors;
    4. 
  
  
  
  
  4. }
    5.

图片来源力扣

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

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

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

可能的一个图

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

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

模拟克隆的过程

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

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

如果存在那么直接使用HashMap找到对应节点放入克隆图中新创建的List中。

不过不存在说明这个节点第一次遇到，克隆这个节点，先放到hashMap中与被克隆节点对应，然后放入克隆图中新创建的List中。

这个流程其中大概是这样的：

其中一个过程Map的变化和作用

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

 
 
 
 
    
  
  
  
  
  1. /*
    2. 
  
  
  
  
  2. // Definition for a Node.
    3. 
  
  
  
  
  3. class Node {
    4. 
  
  
  
  
  4.     public int val;
    5. 
  
  
  
  
  5.     public List neighbors;
    6. 
  
  
  
  
  6.     public Node() {
    7. 
  
  
  
  
  7.         val = 0;
    8. 
  
  
  
  
  8.         neighbors = new ArrayList();
    9. 
  
  
  
  
  9.     }
    10. 
  
  
  
  
  10.     public Node(int _val) {
    11. 
  
  
  
  
  11.         val = _val;
    12. 
  
  
  
  
  12.         neighbors = new ArrayList();
    13. 
  
  
  
  
  13.     }
    14. 
  
  
  
  
  14.     public Node(int _val, ArrayList _neighbors) {
    15. 
  
  
  
  
  15.         val = _val;
    16. 
  
  
  
  
  16.         neighbors = _neighbors;
    17. 
  
  
  
  
  17.     }
    18. 
  
  
  
  
  18. }
    19. 
  
  
  
  
  19. */
    20. 
  
  
  
  
  20. 
  
  
  
  
  21. class Solution {
    22. 
  
  
  
  
  22.     public Node cloneGraph(Node node) {
    23. 
  
  
  
  
  23.         if(node==null)
    24. 
  
  
  
  
  24.                 return null;
    25. 
  
  
  
  
  25.         Mapmap=new HashMap();//节点映射克隆的节点
    26. 
  
  
  
  
  26. 
  
  
  
  
  27.         Queueoldqueue=new ArrayDeque();//bfs队列
    28. 
  
  
  
  
  28.         oldqueue.add(node);
    29. 
  
  
  
  
  29.         Node value=new Node(node.val);//先将返回的节点 创建、映射
    30. 
  
  
  
  
  30.         map.put(node, value);
    31. 
  
  
  
  
  31.         while (!oldqueue.isEmpty()) {
    32. 
  
  
  
  
  32.             Node oldnode=oldqueue.poll();
    33. 
  
  
  
  
  33.             Node newnode=map.get(oldnode);//找到这个节点对应克隆的映射(一定存在)
    34. 
  
  
  
  
  34.             Listlist=oldnode.neighbors;//邻居
    35. 
  
  
  
  
  35.             Listlistnew=new ArrayList();//克隆邻居
    36. 
  
  
  
  
  36.             for(Node team:list)
    37. 
  
  
  
  
  37.             {
    38. 
  
  
  
  
  38.                 if(map.containsKey(team))
    39. 
  
  
  
  
  39.                 {
    40. 
  
  
  
  
  40.                     listnew.add(map.get(team));
    41. 
  
  
  
  
  41.                     //点以前已经遇到，直接添加到邻居列表
    42. 
  
  
  
  
  42.                 }
    43. 
  
  
  
  
  43.                 else {//这个邻居第一次碰到，需要创建新节点赋予值
    44. 
  
  
  
  
  44.                     Node no=new Node(team.val);
    45. 
  
  
  
  
  45.                     map.put(team, no);//映射
    46. 
  
  
  
  
  46.                     listnew.add(no);
    47. 
  
  
  
  
  47.                     oldqueue.add(team);//这个点第一次遇到，要将它放到队列中进行bfs搜索
    48. 
  
  
  
  
  48.                 }
    49. 
  
  
  
  
  49.             }
    50. 
  
  
  
  
  50.             newnode.neighbors=listnew;//将节点的邻居指向list
    51. 
  
  
  
  
  51.         }
    52. 
  
  
  
  
  52.         return value;
    53. 
  
  
  
  
  53.     }
    54. 
  
  
  
  
  54. }
    55.

结语

到这里，本篇的内容就结束啦，后面也会持续分享一些优秀巧妙的问题、算法，并且多多归纳总结。本篇如果有帮助的话，还请点赞、在看分享一波!

文章名称：刚学会深拷贝一个对象，学妹却问我怎么深拷贝一个图
转载来源：http://www.shufengxianlan.com/qtweb/news34/348834.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

动态网站知识

各行业网站

胜锦安防科技　　 　官网SEO排名　　 　app制作　　 　成都机房机柜租用　　 　工业净化空调　　 　网上商城管理系统　　 　成都app软件开发公司　　 　成都微信小程序开发　　 　成都电商网站建设方案　　 　成都小程序开发　　 　电信机房托管服务器　　 　商城网站　　 　虚拟主机　　 　手机APP开发　　 　信衡房屋鉴定　　 　云服务器　　 　重庆外贸网站建设　　 　成都气球装饰　　 　成都SEO优化公司　　 　乐山中领科信