[[386429]]

本文轉載自微信公眾號「bigsai」，作者bigsai。轉載本文請聯系bigsai公眾號。

前言

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

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

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

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

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

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

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

鄰接矩陣表示一個圖

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

鄰接表表示一個圖

問題分析

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

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

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

圖片來源力扣

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

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

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

可能的一個圖

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

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

模擬克隆的過程

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

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

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

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

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

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

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

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

結語

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