日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關咨詢
選擇下列產(chǎn)品馬上在線溝通
服務時間：8:30-17:00
你可能遇到了下面的問題
關閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
剛學會深拷貝一個對象，學妹卻問我怎么深拷貝一個圖

本文轉(zhuǎn)載自微信公眾號「bigsai」，作者bigsai。轉(zhuǎn)載本文請聯(lián)系bigsai公眾號。

前言

在前面，我寫過一篇Java的深淺拷貝，那是基于對象的拷貝，但放眼數(shù)據(jù)結(jié)構與算法中，你有考慮過怎么拷貝一個圖嗎?(無向圖)

在此之前，你需要對一些概念搞清楚：什么是深拷貝、淺拷貝?

淺拷貝：如果拷貝的是引用類型(非基本類型)，就只會拷貝一層(嵌套的對象不會被拷貝)，如果原對象發(fā)生改變，那么拷貝對象也會發(fā)生改變。

深拷貝：深拷貝的話會拷貝多層，嵌套的對象也會被拷貝出來，相當于開辟一個新的內(nèi)存地址用于存放拷貝的對象。

用通俗一點(可能不完全確切)的話解釋，淺拷貝就像你的雙胞胎兄弟一樣，你們父母親人都是一樣的;而深拷貝就像另一個平行的時空，那里有另一個你的一切。

既然搞懂了深淺拷貝以及其區(qū)別，我們再看看圖，圖一般用來表示節(jié)點和節(jié)點之間的關系，常分為有向圖和無向圖，在這里我們以無向圖(一旦連接即雙向)為主題。

我們對圖的表示一般有鄰接矩陣和鄰接表，鄰接矩陣的話比較直觀的表示一個圖的連通性，操作維護更簡單，在Java中一般使用二維數(shù)組表示鄰接矩陣，數(shù)組中的值可以表示兩個節(jié)點的權值。

鄰接矩陣表示一個圖

使用鄰接矩陣雖然簡單但是有個比較差的就是浪費較多內(nèi)存空間，所以很多情況還是使用鄰接表來表示一個圖，鄰接表一般是數(shù)組+鏈表的這么一個組合。但是也有一些特殊情況各個節(jié)點比較獨立的不用數(shù)組聯(lián)立。

鄰接表表示一個圖

問題分析

如果這個圖使用鄰接表表示，給你無向 連通 圖中一個節(jié)點的引用，請你返回該圖的 深拷貝(克隆)，這個問題是力扣131克隆圖原題。

圖中的每個節(jié)點都包含它的值 val(int) 和其鄰居的列表(list[Node])。

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

圖片來源力扣

給一個節(jié)點的引用，怎么克隆這個圖呢?

如果只有這一個節(jié)點，那么克隆這個節(jié)點就好。如果這個節(jié)點只有一層鄰居，那克隆這個鄰居的列表(克隆List集合)即可。

但事實是這個節(jié)點可能有多層鄰居，并且鄰居之間可能存在著復雜聯(lián)系。

可能的一個圖

克隆整個圖，所以圖的每一個節(jié)點都要被克隆的，我們需要使用圖論的搜索算法來枚舉所有節(jié)點，并且在遍歷的過程中我們需要想辦法將節(jié)點之間的關系也克隆下來。遍歷的方法可以使用dfs或者bfs，這里使用bfs來實現(xiàn)。

凡是遇到苦難的時候我們模擬一下這個克隆的過程即可，通過下面這張圖可以大概了解克隆圖的過程中，最大的問題是要避免創(chuàng)建重復節(jié)點。即有的節(jié)點一旦被創(chuàng)建它的引用可能在后面會被用到的。

模擬克隆的過程

那我們該如何解決這個問題呢?怎么樣能夠快速找到對應節(jié)點的引用?

這里最好的方法是使用HashMap，其中key保存的是被克隆圖中的節(jié)點，而value是在克隆圖中所對應的節(jié)點，這樣在克隆新圖的過程中，我們遍歷被克隆圖中節(jié)點鄰居的時候，就可以用哈希判斷這個節(jié)點對應的value是否存在(即這個節(jié)點在克隆圖中是否存在)。

如果存在那么直接使用HashMap找到對應節(jié)點放入克隆圖中新創(chuàng)建的List中。

不過不存在說明這個節(jié)點第一次遇到，克隆這個節(jié)點，先放到hashMap中與被克隆節(jié)點對應，然后放入克隆圖中新創(chuàng)建的List中。

這個流程其中大概是這樣的：

其中一個過程Map的變化和作用

有了上面的分析，想必你對這個問題的解決已經(jīng)有了思路和想法，下面就提供一下代碼實現(xiàn)。

 
 
 
 
    
  
  
  
  
  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();//節(jié)點映射克隆的節(jié)點
    26. 
  
  
  
  
  26. 
  
  
  
  
  27.         Queueoldqueue=new ArrayDeque();//bfs隊列
    28. 
  
  
  
  
  28.         oldqueue.add(node);
    29. 
  
  
  
  
  29.         Node value=new Node(node.val);//先將返回的節(jié)點 創(chuàng)建、映射
    30. 
  
  
  
  
  30.         map.put(node, value);
    31. 
  
  
  
  
  31.         while (!oldqueue.isEmpty()) {
    32. 
  
  
  
  
  32.             Node oldnode=oldqueue.poll();
    33. 
  
  
  
  
  33.             Node newnode=map.get(oldnode);//找到這個節(jié)點對應克隆的映射(一定存在)
    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.                     //點以前已經(jīng)遇到，直接添加到鄰居列表
    42. 
  
  
  
  
  42.                 }
    43. 
  
  
  
  
  43.                 else {//這個鄰居第一次碰到，需要創(chuàng)建新節(jié)點賦予值
    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;//將節(jié)點的鄰居指向list
    51. 
  
  
  
  
  51.         }
    52. 
  
  
  
  
  52.         return value;
    53. 
  
  
  
  
  53.     }
    54. 
  
  
  
  
  54. }
    55.

結(jié)語

到這里，本篇的內(nèi)容就結(jié)束啦，后面也會持續(xù)分享一些優(yōu)秀巧妙的問題、算法，并且多多歸納總結(jié)。本篇如果有幫助的話，還請點贊、在看分享一波!


網(wǎng)站欄目：剛學會深拷貝一個對象，學妹卻問我怎么深拷貝一個圖
網(wǎng)站地址：http://www.dlmjj.cn/article/dpioihd.html