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

給定無向連通圖中一個節(jié)點的引用，返回該圖的深拷貝（克隆）。圖中的每個節(jié)點都包含它的值 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é)點 1 的值是 1，它有兩個鄰居：節(jié)點 2 和 4 。
節(jié)點 2 的值是 2，它有兩個鄰居：節(jié)點 1 和 3 。
節(jié)點 3 的值是 3，它有兩個鄰居：節(jié)點 2 和 4 。
節(jié)點 4 的值是 4，它有兩個鄰居：節(jié)點 1 和 3 。

提示：

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

無向圖是一個簡單圖，這意味著圖中沒有重復的邊，也沒有自環(huán)。

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

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

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.

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

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

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

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

Java：

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

Python3：

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

遞歸完成的深度優(yōu)先搜索非常簡潔，比較容易理解，唯一要注意的就是需要把字典定義在函數(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é)點并建立映射關系
        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時可以 dict().get(key) 也可以 dict[key] 時間復雜度都為1，但是在做算法題時肯定要用 dict[key] 這種方式。因為 get() 方法雖然效果一樣，但是反復調(diào)用函數(shù)造成的時間消耗非常高，python語言本來就慢，應該養(yǎng)成盡可能優(yōu)化代碼的習慣。

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