文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2024-12-03 09:52

关注

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

前言

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

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

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

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

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

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

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

邻接矩阵表示一个图

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

邻接表表示一个图

问题分析

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

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

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

图片来源力扣

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

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

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

可能的一个图

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

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

模拟克隆的过程

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

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

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

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

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

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

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

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

结语

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

 

来源: bigsai内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯