本文详解 leetcode 133. clone graph 的 dfs 深拷贝实现要点，重点解决因忽略图中环导致的重复节点创建问题，并提供简洁、健壮、可复用的递归解决方案。
在实现无向图的深拷贝时，一个常见误区是仅用 set 记录已访问节点值（如 visited = set()），却未保存对应克隆节点的引用。这会导致同一原始节点被多次克隆——尤其当图中存在环（cycle）或多个入边时，违反“深拷贝”要求（即结构一致 + 引用独立 + 节点唯一），最终使输出图结构错误，无法通过 LeetCode 测试用例。
核心问题在于：DFS 遍历中，若邻居节点 neighbor 已被访问过，你不应新建 Node(neighbor.val)，而应复用此前已创建的克隆节点。为此，visited 必须从 set 升级为哈希映射（dict），以支持“值 → 克隆节点”的快速查找与复用。
以下是推荐的正确实现（带详细注释）：
"""
# 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: {original_node.val -> cloned_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]
# 否则创建新节点，并立即加入 visited（避免后续递归重复创建）
clone = Node(n.val)
visited[n.val] = clone
# 递归克隆所有邻居，并挂载到当前克隆节点上
for neighbor in n.neighbors:
clone.neighbors.append(dfs(neighbor))
return clone
return dfs(node)✅ 关键设计亮点：
-
状态复用而非标记跳过：visited 存储的是
映射，而非布尔标记；每次进入 dfs 先查表，命中即复用，确保每个原始节点至多生成一个克隆体。 - 无特殊边界处理：空节点、单节点、孤立节点等均由 dfs 统一处理，逻辑更简洁、鲁棒性更强。
- 返回式递归：dfs 返回克隆节点，消除副作用参数（如原代码中的 copy 参数），符合函数式风格，降低出错概率。
⚠️ 注意事项：
- 不可使用 id(node) 或 node 对象本身作为字典 key（因图中节点可能重复 val 但不同实例，且 LeetCode 测试环境对象身份不稳定）；必须用 node.val 作为键（题设保证节点值唯一）。
- neighbors 列表必须逐个 dfs 递归填充，不可浅拷贝（如 copy.neighbors = n.neighbors[:]），否则仍共享原始引用。
- 本解法时间复杂度为 O(N + E)，空间复杂度为 O(N)（递归栈 + visited 字典），符合最优要求。
该方案已通过 LeetCode 所有测试用例（包括含环图、大图、单节点图等），是解决图深拷贝问题的标准范式。
