本文详解如何用 dfs 正确实现无向连通图的深拷贝，重点解决因忽略图中环而导致的重复节点创建问题，并提供简洁、健壮、可复用的递归解决方案。
在 LeetCode 133. Clone Graph 中，目标是为给定的连通无向图生成一个完全独立的深拷贝——即新图中每个节点及其邻接关系都需全新构造，且任意两个节点间的关系（尤其是环结构）必须与原图严格一致。常见错误（如题中原始代码）在于仅用 set 记录已访问的 val 值，却未保存对应克隆节点的引用，导致遇到已访问节点时仍新建节点，破坏图结构一致性。
核心问题在于：图可能含环，而深拷贝必须复用已创建的克隆节点，而非重复实例化。
因此，状态映射容器不能只是 visited: Set[int]，而应升级为 visited: Dict[int, Node]，以支持“查表复用”——当 DFS 再次抵达某 val 对应的节点时，直接返回其已有克隆体。
以下是推荐的 DFS 实现（清晰版）：
"""
# Definition for a Node.
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
from typing import Optional, Dict
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
visited: Dict[int, 'Node'] = {}
def dfs(n: Optional['Node']) -> Optional['Node']:
if not n:
return None
if n.val in visited:
return visited[n.val] # 复用已克隆节点，避免环导致重复创建
clone = Node(n.val) # 创建新节点
visited[n.val] = clone # 立即注册，防止后续递归重复创建
# 递归克隆所有邻居，并追加到当前克隆节点的 neighbors 列表
for neighbor in n.neighbors:
clone.neighbors.append(dfs(neighbor))
return clone
return dfs(node)✅ 关键设计亮点：
- 返回式递归：dfs() 返回克隆后的节点，消除冗余参数，逻辑更内聚；
- 即时注册：在创建 clone 后立即存入 visited，确保同一节点值在任何调用栈深度下均命中缓存；
- 零特判：无需单独处理 node is None 或 len(node.neighbors) == 0，递归自然覆盖所有边界情况；
- 强类型提示：显式标注 Dict[int, 'Node'] 和返回类型，提升可读性与 IDE 支持。
⚠️ 注意事项：
- 节点 val 在题目中保证唯一（1-indexed 且无重复），故可用 val 作哈希键；若实际场景中 val 不唯一，则必须改用 id(node) 或自定义唯一标识；
- 本解法时间复杂度为 O(N + E)（N 为节点数，E 为边数），空间复杂度为 O(N)（哈希表 + 递归栈）；
- 若需迭代式 DFS/BFS 实现，可配合栈/队列 + 同样 Dict[int, Node] 映射完成，原理一致。
该方案已通过 LeetCode 全部测试用例（包括含环图如 [[2,4],[1,3],[2,4],[1,3]]），是图深拷贝问题的标准范式。
