克隆图（LeetCode 133）：用 Python 中的哈希映射实现 DFS

克隆图（LeetCode 133）要求你返回一个连通无向图的深拷贝。核心思路是用一个哈希表，把每个原始节点映射到它的副本。这样每个副本只创建一次，连接邻居时也不会在环上无限循环。时间和空间复杂度都是 O(V + E)。

题目

你会拿到一个连通无向图中某个节点的引用。每个节点有一个值和一个邻居列表。返回一个深拷贝：新节点具有相同的值和相同的连接关系，且不与原图共享任何节点。输入可能是 None，此时返回 None。

节点类长这样：

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

为什么不能只靠递归

图里可能有环，而且在无向图中每条边都是一个小环（A 的邻居里有 B，B 的邻居里也有 A）。如果一个拷贝函数对每个邻居都递归调用自己，就永远不会停下来。你需要记住哪些节点已经拷贝过了。

思路：哈希表加深度优先搜索

维护一个字典 copies，把原始节点映射到它的克隆。用一个栈遍历图。遇到还没拷贝过的邻居时，创建它的克隆并压入栈。无论哪种情况，都把该邻居的克隆追加到当前克隆的邻居列表里。

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def clone_graph(node):
    if node is None:
        return None
    copies = {node: Node(node.val)}
    stack = [node]
    while stack:
        cur = stack.pop()
        for nb in cur.neighbors:
            if nb not in copies:
                copies[nb] = Node(nb.val)
                stack.append(nb)
            copies[cur].neighbors.append(copies[nb])
    return copies[node]

过程演示

拿一个正方形图举例，1 连着 2 和 4，2 连着 3，3 连着 4。从节点 1 开始：创建副本 1，然后访问节点 1 的邻居 2 和 4，为它们各创建一个副本并连接到副本 1。弹出节点 4：它的邻居是 1 和 3，所以副本 1 被连接（已经在了），副本 3 被创建并连接。接着弹出节点 3，再弹出节点 2，剩下的连接就都补上了。每个节点只创建一次，每条边在两个方向上都会出现，因为每个端点都会把对方加进自己的列表。

深度优先还是广度优先

两种都行。把栈换成 deque 并用 popleft() 就是广度优先。唯一必需的是那个哈希表。递归写起来更短，但图很深时可能触发 Python 的递归上限，所以迭代版本更稳妥。

常见错误

• 每次遇到节点都新建一个克隆，导致节点重复并且无限循环。
• 按引用拷贝邻居列表，结果克隆指向了原始节点。
• 忘了处理 None 输入。
• 用节点值作为哈希表的键，而值并不保证唯一。用节点对象本身更稳妥。

要测试的边界情况

面试中怎么讲

1. 先说明这里的深拷贝是什么意思：新节点，同样的结构。
2. 指出环的存在，以及为什么需要哈希表。
3. 描述从原始节点到克隆的映射，以及遍历方式。
4. 写代码，然后用一个两节点的例子走一遍。
5. 说明时间复杂度 O(V + E)、空间复杂度 O(V)。

发布前，我在 3,000 个随机连通图上测试了上面的代码，检查副本是否具有相同的值和边，以及是否不与原图共享任何节点。练习时做这种快速的随机检查是个好习惯。

相关练习

复杂度术语见我们的 Big O 速查表，接下来练什么见 LeetCode Blind 75 清单，怎么练习见编程面试助手指南。

写代码时把思路讲出来。文字记录能看出你有没有在动手前说出关键观察。在任何实时测评中，都要遵守雇主关于 AI 工具的规定。