Clone Graph：编码问题解决方案详解
Source: Dev.to
“Clone Graph” 问题要求你为一个连通图创建 深拷贝。
图中的每个节点都包含一个值以及其邻居列表。克隆后的图必须使用全新的节点，但必须完整保留原图的结构，包括所有连接和环路。换句话说，原图中的每一个节点‑边关系都必须在克隆图中得到对应，而不能复用任何原始对象。
这个问题并不是单纯地复制数值，而是复制关系。真正的挑战在于正确地重建图的拓扑结构，尤其是在出现环路和共享邻居的情况下。
为什么朴素复制会失败
- 朴素的方法可能会尝试递归复制每个节点及其邻居。当图中存在环时，这种方法很快就会失效。如果不进行仔细处理，算法会陷入无限递归，不断尝试克隆相同的节点。
- 另一个常见错误是 多次复制节点。如果原始图中的两个节点都引用同一个邻居，克隆后也必须只引用该邻居的 单一克隆版本，而不是两个独立的副本。未能保持这种一对一对应会导致图结构不正确。
查看 Island Perimeter 编码题解，以了解处理边缘情况的示例。
认识到映射的必要性
关键的洞察在于，克隆图本质上是关于 维护原始节点与其克隆对应节点之间的映射。每当你克隆一个节点时，必须记住该克隆，以便在以后再次遇到原始节点时能够复用它。
映射有两个作用：
- 防止在图中存在循环时出现无限循环。
- 确保结构一致性，保证每个原始节点恰好对应一个克隆节点。
图遍历作为基础
要克隆图，你必须访问每个节点并检查其邻居。这自然会使用图遍历技术，例如 深度优先搜索 (DFS) 或 广度优先搜索 (BFS)。只要系统地探索所有可达节点，任一策略都可行。
在遍历过程中，首先检查映射：
- 如果当前节点已经被克隆，则直接返回已有的克隆对象。
- 如果没有，则创建一个新的克隆对象，将其存入映射中，然后继续克隆其邻居节点。
另请参阅以下题目的解答：
Sum of Left Leaves 和
Bitwise AND of Numbers Range。
为什么深度优先和广度优先都可行
- DFS 通常概念上更简单，因为它映射了图的递归定义：克隆一个节点，然后递归克隆它的邻居。
- BFS 使用队列逐层处理节点。
两种方法都是正确的，因为映射保证每个节点恰好被克隆一次，无论遍历顺序如何。选择哪一种主要取决于个人风格和使用习惯。
处理循环安全
循环是使这个问题有趣的地方。在循环图中，你可以通过不同的路径再次访问同一个节点。如果没有映射，这会导致无限递归或重复克隆。
有了映射，循环就变得无害。当再次遇到之前访问过的节点时，算法只会从映射中检索其克隆并链接到它，从而在克隆图中完美保留循环结构。
正确构建邻居关系
仅克隆节点是不够的；还必须重建每个节点的邻居列表。这通过遍历原始节点的邻居并将相应的克隆邻居附加到克隆节点来完成。
由于邻居可能已经或尚未被克隆，此步骤依赖递归调用（DFS）或队列遍历步骤（BFS）。映射确保邻居引用始终指向正确的克隆对象。
为什么这种方法能保证正确性
- 每个原始节点仅被访问并克隆一次。
- 每条原始边都在对应的克隆节点之间重新创建。
由于映射强制了一对一对应，且遍历确保了完整覆盖，克隆后的图在结构上与原始图完全相同，且两者之间没有共享引用。
时间和空间复杂度考虑
- 时间: (O(N + E)) – 与节点数 (N) 和边数 (E) 成线性关系，因为每个节点和每条边只会被处理一次。
- 空间: (O(N)) – 用于映射以及递归栈（DFS）或队列（BFS）。
这种效率对于图的克隆是最优的；你不可能克隆的节点或边比原图中存在的更少。
为什么这个问题在面试中常见
Clone Graph 是一个经典的面试题，因为它可以测试候选人是否真正理解：
- 图遍历技术。
- 浅拷贝和深拷贝的区别。
- 对循环的正确处理。
它还检查在遍历过程中使用辅助数据结构（例如哈希映射）来保持关系的能力。
该问题超出图克隆的教学内容
除了具体任务外，这个问题还阐明了一个关于复制 互联数据结构 的更广泛的教训。每当对象相互引用时，克隆需要跟踪身份，而不仅仅是值。
如果你能清晰地解释映射为何必不可少、遍历如何安全地探索图以及循环如何在无需特殊情况的情况下处理，你就展示了强大的算法推理能力。这种深度的理解使得 “Clone Graph” 成为一个卓越的练习。
在图遍历、内存管理和深拷贝语义方面的优秀练习。
如果你想了解更多编码问题的解释，请查看：