摘要：解題思路涉及到圖的遍歷無(wú)非就是深度優(yōu)先搜索廣度優(yōu)先搜索，可以先看前幾日的這篇文章就需要借助隊(duì)列實(shí)現(xiàn)，可以借助棧也可以直接用遞歸實(shí)現(xiàn)。

給定無(wú)向連通圖中一個(gè)節(jié)點(diǎn)的引用，返回該圖的深拷貝（克?。D中的每個(gè)節(jié)點(diǎn)都包含它的值 val（Int） 和其鄰居的列表（list[Node]）。

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

示例：

輸入：
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

解釋：
節(jié)點(diǎn) 1 的值是 1，它有兩個(gè)鄰居：節(jié)點(diǎn) 2 和 4 。
節(jié)點(diǎn) 2 的值是 2，它有兩個(gè)鄰居：節(jié)點(diǎn) 1 和 3 。
節(jié)點(diǎn) 3 的值是 3，它有兩個(gè)鄰居：節(jié)點(diǎn) 2 和 4 。
節(jié)點(diǎn) 4 的值是 4，它有兩個(gè)鄰居：節(jié)點(diǎn) 1 和 3 。

提示：

節(jié)點(diǎn)數(shù)介于 1 到 100 之間。

無(wú)向圖是一個(gè)簡(jiǎn)單圖，這意味著圖中沒(méi)有重復(fù)的邊，也沒(méi)有自環(huán)。

由于圖是無(wú)向的，如果節(jié)點(diǎn) p 是節(jié)點(diǎn) q 的鄰居，那么節(jié)點(diǎn) q 也必須是節(jié)點(diǎn) p 的鄰居。

必須將給定節(jié)點(diǎn)的拷貝作為對(duì)克隆圖的引用返回。

Note:

The number of nodes will be between 1 and 100.

The undirected graph is a simple graph#Simple_graph), which means no repeated edges and no self-loops in the graph.

Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.

You must return the copy of the given node as a reference to the cloned graph.

涉及到圖的遍歷無(wú)非就是DFS（深度優(yōu)先搜索）、BFS（廣度優(yōu)先搜索），可以先看前幾日的這篇文章：

BFS就需要借助隊(duì)列實(shí)現(xiàn)，DFS可以借助棧也可以直接用遞歸實(shí)現(xiàn)。就這道題而言直接用遞歸更好一些，無(wú)需開辟額外的數(shù)據(jù)結(jié)構(gòu)空間記錄節(jié)點(diǎn)。BFS、DFS寫法相對(duì)固定，建議花點(diǎn)時(shí)間一次性理解透，一勞永逸。

這道題思路很清晰，關(guān)鍵點(diǎn)是如何深拷貝隨機(jī)節(jié)點(diǎn)，可以參考鏈表的這篇文章：LeetCode 138：復(fù)制帶隨機(jī)指針的鏈表 Copy List with Random Pointer

鏈表是線性的，可以 復(fù)制節(jié)點(diǎn)到每個(gè)節(jié)點(diǎn)之后，很巧妙的完成深拷貝。顯然圖這樣的樹狀結(jié)構(gòu)無(wú)法用這種方法，只能借助數(shù)據(jù)結(jié)構(gòu)記錄已拷貝過(guò)的節(jié)點(diǎn)。這種需要映射新舊節(jié)點(diǎn)關(guān)系自然就是用散列表（字典）。

Java：

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return node;
        Queue queue = new LinkedList<>();//借助隊(duì)列實(shí)現(xiàn)BFS
        Map map = new HashMap<>();//哈希映射
        Node head = new Node(node.val, new ArrayList<>());//頭節(jié)點(diǎn)
        map.put(node, head);//哈希映射原節(jié)點(diǎn)和新節(jié)點(diǎn)
        queue.add(node);//原節(jié)點(diǎn)加入到隊(duì)列
        while (!queue.isEmpty()) {//隊(duì)列不為空就重復(fù)循環(huán)
            Node tmp = queue.poll();//彈出隊(duì)列頭節(jié)點(diǎn)
            for (Node n : tmp.neighbors) {//遍歷鄰居節(jié)點(diǎn)
                if (!map.containsKey(n)) {//字典的鍵不包含該節(jié)點(diǎn)時(shí)
                    map.put(n, new Node(n.val, new ArrayList<>()));//新建映射關(guān)系加入字典
                    queue.add(n);//加入隊(duì)列
                }
                map.get(tmp).neighbors.add(map.get(n));//加入鄰居節(jié)點(diǎn)
            }
        }
        return head;
    }
}

Python3：

class Solution:
    def cloneGraph(self, node: "Node") -> "Node":
        if not node: return node
        head = Node(node.val, [])#頭節(jié)點(diǎn)
        map = {node: head}#初始化字典，并建立新舊節(jié)點(diǎn)的映射關(guān)系
        queue = collections.deque()#隊(duì)列
        queue.append(node)#原節(jié)點(diǎn)加入隊(duì)列
        while queue:#隊(duì)列不為空
            tmp = queue.popleft()#彈出隊(duì)列頭節(jié)點(diǎn)
            for n in tmp.neighbors:#遍歷鄰居節(jié)點(diǎn)
                if n in map.keys():#n節(jié)點(diǎn)存在于字典的鍵里時(shí)
                    map[tmp].neighbors.append(map[n])#直接加入到新節(jié)點(diǎn)的鄰居節(jié)點(diǎn)
                else:
                    map[n] = Node(n.val, [])#新建節(jié)點(diǎn)并建立映射關(guān)系
                    map[tmp].neighbors.append(map[n])#由新建的映射關(guān)系取出節(jié)點(diǎn)并加入鄰居節(jié)點(diǎn)
                    queue.append(n)#該鄰居節(jié)點(diǎn)加入隊(duì)列
        return head

遞歸完成的深度優(yōu)先搜索非常簡(jiǎn)潔，比較容易理解，唯一要注意的就是需要把字典定義在函數(shù)外。

Java：

class Solution {
    Map map = new HashMap();

    public Node cloneGraph(Node node) {
        if (node == null) return node;
        map.put(node, new Node(node.val, new ArrayList<>()));//每次都要新建節(jié)點(diǎn)并建立映射關(guān)系
        for (Node n : node.neighbors) {
            if (map.containsKey(n)) map.get(node).neighbors.add(map.get(n));
            else map.get(node).neighbors.add(cloneGraph(n));
        }
        return map.get(node);
    }
}

Python3：

class Solution:
    map = dict()

    def cloneGraph(self, node: "Node") -> "Node":
        if not node: return node
        self.map[node] = Node(node.val, [])
        for n in node.neighbors:
            if n in self.map.keys():
                self.map[node].neighbors.append(self.map[n])
            else:
                self.map[node].neighbors.append(self.cloneGraph(n))
        return self.map[node]

注意：

python中的字典取values時(shí)可以 dict().get(key) 也可以 dict[key] 時(shí)間復(fù)雜度都為1，但是在做算法題時(shí)肯定要用 dict[key] 這種方式。因?yàn)?get() 方法雖然效果一樣，但是反復(fù)調(diào)用函數(shù)造成的時(shí)間消耗非常高，python語(yǔ)言本來(lái)就慢，應(yīng)該養(yǎng)成盡可能優(yōu)化代碼的習(xí)慣。

歡迎關(guān)注微.信公.眾號(hào)：愛寫B(tài)ug