克隆图为什么要用哈希表？DFS 和 BFS 如何实现深拷贝？

简化版

克隆图要做深拷贝：每个原节点都要对应一个新节点，边关系也要复制。因为图可能有环，必须用哈希表记录“原节点 -> 克隆节点”，既防止重复创建，也防止 DFS/BFS 陷入死循环。

详细版

核心是维护映射 Map<Node, Node> visited。如果当前原节点没克隆过，就先创建它的克隆节点放入 map；然后遍历原节点的邻居，把每个邻居的克隆节点加入当前克隆节点的邻居列表。邻居如果没克隆过，就递归 DFS 或放入 BFS 队列继续处理。

DFS 更自然：函数返回当前节点的克隆体，遇到已经克隆过的节点直接返回 map 里的对象。BFS 更显式：从起点入队，逐层遍历原图，遇到新邻居就创建克隆节点并入队。两者复杂度都是 O(V + E)，空间复杂度 O(V)。

完整版教学

一、克隆图难在哪里

如果图是一棵树，复制节点时从根往下复制即可，因为每个节点只有一条父路径。但图可能有环，也可能有多个节点指向同一个邻居。如果不记录“哪些原节点已经克隆过”，同一个节点会被复制多次，环还会导致无限递归。

例如三角形图：

1 --- 2
 \   /
   3

从 1 克隆到 2，再从 2 克隆到 3，再从 3 回到 1，如果没有 map，程序会再次克隆 1，然后继续绕圈。哈希表的作用就是给每个原节点建立唯一身份证：原节点只创建一次克隆节点，之后所有边都指向这一个克隆对象。

二、哈希表保存的不是访问状态，而是对象映射

普通 DFS 的 visited 只需要记录某个节点是否访问过；克隆图的 map 更强，它记录的是 oldNode -> newNode。这使我们既能判断是否访问过，也能拿到已经创建好的克隆对象。

普通遍历 visited	克隆图 map
只判断是否访问过	判断是否访问过，并返回克隆节点
值通常是 boolean	值是新创建的 Node
防止重复走	防止重复创建和死循环

假设原图有 4 个节点、5 条无向边。最终 map 中应该有 4 条记录，而克隆图邻接表里会复制出 10 个邻居引用，因为无向边在两个端点的 neighbors 中各出现一次。

三、DFS 递归实现

DFS 写法的关键是“先创建当前节点，再递归处理邻居”。先放入 map 很重要，因为后续邻居可能马上通过环指回当前节点；如果等邻居都处理完再放 map，就挡不住环。

class Solution {
    private Map<Node, Node> map = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (map.containsKey(node)) return map.get(node);

        Node copy = new Node(node.val);
        map.put(node, copy);
        for (Node nei : node.neighbors) {
            copy.neighbors.add(cloneGraph(nei));
        }
        return copy;
    }
}

这个函数的返回值是“当前原节点对应的克隆节点”。递归边界不是叶子节点，而是“这个节点已经在 map 里”。图没有叶子概念，环图里尤其不能按树的思路找终点。

四、BFS 迭代实现

BFS 的思路是从起点开始，把原节点放进队列。每弹出一个原节点，就遍历它的所有邻居；如果邻居没有克隆过，立刻创建克隆节点并入队；然后把邻居的克隆节点连到当前克隆节点上。

创建 copy(start)，start 入队
while queue not empty:
  cur = poll()
  for nei in cur.neighbors:
    if nei not in map:
      map[nei] = new Node(nei.val)
      queue.offer(nei)
    map[cur].neighbors.add(map[nei])

BFS 的优势是不会吃递归栈，适合节点数量很大或语言递归限制较低的场景。DFS 更短，BFS 更稳定；面试时任选一种写清楚即可。

五、深拷贝要复制节点和边

深拷贝不是只复制节点值，也不是复用原 neighbors。新图的每个节点都应该是新对象，且新对象之间的连接关系与原图一致。判断是否是深拷贝，可以用两个条件：对象地址不同，结构关系相同。

原图: A -> [B, C]
克隆: A' -> [B', C']

正确: A' != A, B' != B, C' != C
错误: A' 的 neighbors 里直接放 B 或 C

如果复用原节点，修改克隆图会影响原图；这违反了深拷贝语义。这个追问经常用来区分“会写遍历”和“理解对象引用”的候选人。

六、复杂度怎么分析

每个节点最多被创建一次，每条邻接关系最多被扫描一次，所以时间复杂度是 O(V + E)。对于无向图，如果输入邻接表中每条边出现两次，扫描的是邻接表长度，仍然写成 O(V + E)，其中 E 可以按逻辑边或邻接项口径说明清楚。

空间复杂度主要来自 map，保存 V 个映射；DFS 还有递归栈，最坏 O(V)；BFS 有队列，最坏也是 O(V)。如果图为空，返回 null，不要创建多余节点。

七、常见误区与追问

记忆钩子：克隆图先建“原到新”的字典，再按原图边关系给新节点连边；没有这张字典，环和共享邻居都会出问题。

误区：用节点值当哈希表 key。 节点值不一定能代表对象唯一性，应该用原节点对象本身作为 key。
误区：先递归完邻居再把当前节点放入 map。 有环时会在邻居回指当前节点时无限递归，必须先放 map。
误区：克隆节点后直接复用原 neighbors。 这只是浅拷贝，新图仍然指向旧节点，修改会互相影响。
追问：DFS 和 BFS 哪个更好？ 两者复杂度相同，DFS 简洁，BFS 避免递归栈风险。
追问：如果图不连通怎么办？ 题目若只给一个起点，克隆起点可达的连通分量；如果要求克隆整张图，需要遍历所有节点作为入口。
追问：为什么复杂度不是 O(VE)？ 因为 map 保证每个节点只创建一次，每条邻接关系只处理常数次。

八、加强记忆

克隆图的主线是“唯一映射 + 复制边”。Map<原节点, 新节点> 同时解决三件事：判断是否已访问、防止环导致死循环、确保共享邻居只克隆一次。DFS 写成递归返回克隆节点，BFS 写成队列逐层扩展；不管哪种写法，最后都要保证新图对象独立、结构一致。

简化版

详细版