跳到主要内容

LeetCode 133. 克隆图

本节目标

先登记原节点到副本节点的映射，再递归复制邻接关系以处理环。

这是图的表示与遍历中“visited 承载更多信息”的例子：它不只是说明节点访问过，还记录原节点对应的唯一副本。

查看 LeetCode 原题

题意与约束​

给定无向连通图中一个节点，返回整张图的深拷贝。副本节点不能与原图共用身份；副本中的边必须指向副本节点。输入可能为空，图也可能含环。

直接思路与瓶颈​

只递归创建当前节点再递归邻居，会在环上无限递归；即使在无环图中按值查找已创建节点，也无法可靠处理同值对象，更会把共享邻居错误复制成多个节点。

图模型与算法推导​

维护 memo：键是原节点对象，值是它的副本。处理节点时先查 memo，存在则直接返回；不存在时先创建副本并立刻写入 memo，再递归克隆每个邻居并加入副本邻接表。这样递归走到回边时能取得已登记的副本，不会重新创建或继续展开。

正确性依据​

不变量是：对每个已登记原节点，memo 中恰有一个不同身份的副本，且已处理的邻接边都连接到相应副本。首次处理节点时先建立这一一对应，之后递归假设保证邻居返回其唯一副本；把它加入邻接表保持边关系。memo 命中时直接返回已有副本保证共享节点与环被保留。于是可达的每个原节点恰克隆一次，每条邻接关系也被复制。

样例执行过程​

设原图有两个对象 A(val=1)、B(val=2)，邻接关系为 A.neighbors=[B]、B.neighbors=[A]。调用 clone(A) 时，copies 先登记 {A: A'}；递归邻居 B 时登记为 {A: A', B: B'}。B 的邻居又是 A，查询 copies[A] 命中 A'，因此 B' 的邻接表加入 A' 而不再递归。返回上一层后，A' 的邻接表加入 B'；最终 A' ↔ B'，并且 A'、B' 分别与 A、B 身份不同。

代码实现​

C++17
#include <functional>
#include <unordered_map>

using namespace std;

class Solution {
public:
    Node* cloneGraph(Node* node) {
        unordered_map<Node*, Node*> copies;
        function<Node*(Node*)> clone = [&](Node* current) -> Node* {
            if (current == nullptr) return nullptr;
            auto found = copies.find(current);
            if (found != copies.end()) return found->second;

            Node* copy = new Node(current->val);
            copies[current] = copy;
            for (Node* neighbor : current->neighbors) {
                copy->neighbors.push_back(clone(neighbor));
            }
            return copy;
        };
        return clone(node);
    }
};

测试用包装器定义平台 Node，检查空图、根节点身份、邻接顺序与回边；断言从未按节点值代替对象身份。

复杂度分析​

每个节点和每条邻接边各处理一次，时间复杂度为 O(V + E)。memo 与递归栈的额外空间为 O(V)。

边界与易错点​

  • nullptr / None 应直接返回空。
  • 必须在递归邻居前写入 memo，否则环无法终止。
  • memo 的键是节点对象（指针/引用），不是 val。
  • 副本邻居应指向 clone 结果，不能把原邻居直接塞入副本。

模式迁移​

当遍历需要保留“首次到达时建立的对象或状态”时，可把布尔 visited 升级为映射：复制随机链表、序列化图、构造父节点映射都遵循先登记、再扩张的顺序。