1. 使用哈希表 `visited` 来存储原图中被访问过的节点和克隆图中对应节点，键值对为 原图被访问过的节点：克隆图中对应节点。

visited = dict()

if node in visited:

return visited[node]

visited[node] = clone_node

1. 使用哈希表 `visited` 来存储原图中被访问过的节点和克隆图中对应节点，键值对为 原图被访问过的节点：克隆图中对应节点。使用队列`queue` 存放节点。

2. 根据起始节点，创建一个新的节点，并将其添加到哈希表 `visited` 中，即 `visited[node] = Node(node.val, [])`。然后将起始节点放入队列 `queue`中，即 `queue.append(node)`。

3. 从队列中取出第一个节点 `node_u`。访问节点 `node_u`。

4. 遍历与节点 `node_u` 相连并构成边的节点 `node_v`。

1. 如果 `node_v` 没有被访问过（即 `node_v` 不在 `visited` 中）：

1. 则根据 `node_v` 创建一个新的节点，并将其添加到哈希表 `visited` 中，即 `visited[node_v] = Node(node_v.val, [])`。

2. 然后将 `node_v` 节点放入队列 `queue` 中，即 `queue.append(node_v)`。

5. 重复步骤 3 ~ 4，直到队列 `queue` 为空。

6. 广度优先搜索结束，返回起始节点的克隆节点（即 `visited[node]`）。

class Solution:

def cloneGraph(self, node: 'Node') -> 'Node':

if not node:

return node

visited = dict()

queue = collections.deque()

visited[node] = Node(node.val, [])

queue.append(node)

while queue:

node_u = queue.popleft()

for node_v in node_u.neighbors:

if node_v not in visited:

visited[node_v] = Node(node_v.val, [])

queue.append(node_v)

visited[node_u].neighbors.append(visited[node_v])

return visited[node]

- **时间复杂度**：$O(n)$。其中 $n$ 为图中节点数量。

- **空间复杂度**：$O(n)$。