• 難度： 中等
• 通過率： 25.1%
• 題目鏈接：. - 力扣（LeetCode）

題目描述

克隆一張無向圖，圖中的每個節點包含一個?val?和一個?neighbors?（鄰接點）列表 。

解法：

使用一個 map 來記錄原節點和新節點的映射，然后使用 dfs 來進行 clone。遇到一個節點的時候，如果未克隆過，就克隆該節點并記錄在 map 中，如果此節點已經 clone 過了，那么直接從 map 中得到克隆的節點。

class Solution:def cloneGraph(self, node: 'Node') -> 'Node':new = self.clone(node, {})return newdef clone(self, node, mp):new = Node(node.val, [])mp[node] = newfor neighbor in node.neighbors:if neighbor not in mp:neighbor = self.clone(neighbor, mp)else:neighbor = mp[neighbor]new.neighbors.append(neighbor)return new

也可以使用 bfs 來搞定。

class Solution:def cloneGraph(self, node: 'Node') -> 'Node':new = Node(node.val, [])mp = {node: new}        queue = [node]while queue:node = queue.pop(0)for neighbor in node.neighbors:if neighbor not in mp:mp[neighbor] = Node(neighbor.val, [])queue.append(neighbor)mp[node].neighbors.append(mp[neighbor])return new