剛學(xué)會(huì)深拷貝一個(gè)對(duì)象,學(xué)妹卻問我怎么深拷貝一個(gè)圖

前言

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

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

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

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

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

既然搞懂了深淺拷貝以及其區(qū)別，我們?cè)倏纯磮D，圖一般用來表示節(jié)點(diǎn)和節(jié)點(diǎn)之間的關(guān)系，常分為有向圖和無向圖，在這里我們以無向圖(一旦連接即雙向)為主題。

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

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

問題分析

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

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

class?Node?{
????public?int?val;
????public?List<Node>?neighbors;
}

給一個(gè)節(jié)點(diǎn)的引用，怎么克隆這個(gè)圖呢？

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

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

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

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

那我們?cè)撊绾谓鉀Q這個(gè)問題呢？怎么樣能夠快速找到對(duì)應(yīng)節(jié)點(diǎn)的引用？

這里最好的方法是使用HashMap<Node,Node>，其中key保存的是被克隆圖中的節(jié)點(diǎn)，而value是在克隆圖中所對(duì)應(yīng)的節(jié)點(diǎn)，這樣在克隆新圖的過程中，我們遍歷被克隆圖中節(jié)點(diǎn)鄰居的時(shí)候，就可以用哈希判斷這個(gè)節(jié)點(diǎn)對(duì)應(yīng)的value是否存在(即這個(gè)節(jié)點(diǎn)在克隆圖中是否存在)。

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

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

這個(gè)流程其中大概是這樣的：

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

/*
//?Definition?for?a?Node.
class?Node?{
????public?int?val;
????public?List<Node>?neighbors;
????public?Node()?{
????????val?=?0;
????????neighbors?=?new?ArrayList<Node>();
????}
????public?Node(int?_val)?{
????????val?=?_val;
????????neighbors?=?new?ArrayList<Node>();
????}
????public?Node(int?_val,?ArrayList<Node>?_neighbors)?{
????????val?=?_val;
????????neighbors?=?_neighbors;
????}
}
*/

class?Solution?{
????public?Node?cloneGraph(Node?node)?{
????????if(node==null)
????????????????return?null;
????????Map<Node,?Node>map=new?HashMap<Node,?Node>();//節(jié)點(diǎn)映射克隆的節(jié)點(diǎn)

????????Queue<Node>oldqueue=new?ArrayDeque<Node>();//bfs隊(duì)列
????????oldqueue.add(node);
????????Node?value=new?Node(node.val);//先將返回的節(jié)點(diǎn)?創(chuàng)建、映射
????????map.put(node,?value);
????????while?(!oldqueue.isEmpty())?{
????????????Node?oldnode=oldqueue.poll();
????????????Node?newnode=map.get(oldnode);//找到這個(gè)節(jié)點(diǎn)對(duì)應(yīng)克隆的映射(一定存在)
????????????List<Node>list=oldnode.neighbors;//鄰居
????????????List<Node>listnew=new?ArrayList<Node>();//克隆鄰居
????????????for(Node?team:list)
????????????{
????????????????if(map.containsKey(team))
????????????????{
????????????????????listnew.add(map.get(team));
????????????????????//點(diǎn)以前已經(jīng)遇到，直接添加到鄰居列表
????????????????}
????????????????else?{//這個(gè)鄰居第一次碰到，需要?jiǎng)?chuàng)建新節(jié)點(diǎn)賦予值
????????????????????Node?no=new?Node(team.val);
????????????????????map.put(team,?no);//映射
????????????????????listnew.add(no);
????????????????????oldqueue.add(team);//這個(gè)點(diǎn)第一次遇到，要將它放到隊(duì)列中進(jìn)行bfs搜索
????????????????}
????????????}
????????????newnode.neighbors=listnew;//將節(jié)點(diǎn)的鄰居指向list
????????}
????????return?value;
????}
}

結(jié)語

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

公眾號(hào)剛遷移不久，星標(biāo)用戶都沒了，希望大家能給俺加個(gè)星標(biāo)，不再錯(cuò)過消息！

推薦閱讀：

更多精彩：

點(diǎn)個(gè)在看你最好看