LeetCode 133. 克隆图：DFS 深拷贝的正确实现方法

本文详解如何用 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]]），是图深拷贝问题的标准范式。

# node # app # 栈 # 递归 # int # len # ide # leetcode # 复用 # 图中 # 尤其是 # 已有 # 自定义 # 而非 # 升级为 # 如何用 # 仅用

返回目录在线咨询

上一篇：公章专家在线制作网站官网,专家论证需要盖什么公章？
下一篇：使用smartupload组件实现jsp+jdbc上传下载文件实例解析

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

LeetCode 133. 克隆图：DFS 深拷贝的正确实现方法

您的项目需求