0133. Clone Graph
=================
题目信息
--------
:题号: 0133. 克隆图
:难度: Medium
:主题: 图、深度优先搜索、广度优先搜索、对象映射
:原题: `LeetCode 0133 `_
:重点: 用原节点身份建立唯一副本映射,先登记再展开邻居,从而同时处理环、共享节点和深拷贝
题目重述
--------
给定连通无向图中的一个节点 ``node``,返回整张图的深拷贝。每个原节点都要对应一个新创建的节点,值相同;
原图中的每条邻接关系都要在副本节点之间重建。返回图不能包含任何指向原节点的引用。输入为空时返回
``nullptr``。
自建示例
--------
* 三角形 ``1 -- 2 -- 3 -- 1``:副本也必须形成三角形,但三个节点都使用新地址;
* 若 ``1`` 和 ``2`` 都邻接 ``3``,两个副本的邻接表必须指向同一个 ``clone(3)``,不能各创建一份;
* ``node = nullptr``:图为空,直接返回空指针。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
Node* cloneWithDfs(
Node* original,
std::unordered_map& copies
) {
if (original == nullptr) {
return nullptr;
}
auto found = copies.find(original);
if (found != copies.end()) {
return found->second;
}
Node* copy = new Node(original->val);
copies[original] = copy;
for (Node* originalNeighbor : original->neighbors) {
copy->neighbors.push_back(
cloneWithDfs(originalNeighbor, copies)
);
}
return copy;
}
Node* cloneWithBfs(Node* node) {
if (node == nullptr) {
return nullptr;
}
std::unordered_map copies;
std::queue pending;
copies[node] = new Node(node->val);
pending.push(node);
while (!pending.empty()) {
Node* original = pending.front();
pending.pop();
for (Node* originalNeighbor : original->neighbors) {
if (!copies.count(originalNeighbor)) {
copies[originalNeighbor] =
new Node(originalNeighbor->val);
pending.push(originalNeighbor);
}
copies[original]->neighbors.push_back(
copies[originalNeighbor]
);
}
}
return copies[node];
}
public:
Node* cloneGraph(Node* node) {
std::unordered_map copies;
return cloneWithDfs(node, copies);
}
};
题解
----
深拷贝需要同时复制节点与关系
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
若只新建入口节点,再把原邻接表直接赋给它,返回图中的边仍指向原节点,只是浅拷贝。若对每条邻接引用都
无条件递归创建新节点,问题又变成沿所有图路径展开:无向边会让 ``1 -> 2`` 之后立刻沿 ``2 -> 1`` 返回,
形成无限递归;即使图无环,两个路径汇合到同一节点时也会创建两份副本,破坏共享关系。
真正需要维持的不变量是:每个原节点对象恰好对应一个副本对象。于是核心状态不是“哪些值见过”,而是
``copies[original] = copy`` 的对象身份映射。原节点只作为遍历和哈希键使用,所有新边都必须连接映射右侧的
副本。
为什么不能把 ``val`` 当作通用身份
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
当前题目数据可能保证节点值唯一,但深拷贝的结构语义由节点对象决定,而不是标签决定。若扩展输入允许两个
不同节点拥有相同值,按值建表会错误地把它们合并。使用 ``Node*`` 作为键直接表达“这是同一个原对象”,
也让算法不依赖偶然的值域约束。
递归主解:先登记节点,再复制边
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
``cloneWithDfs`` 对首次遇到的 ``original`` 分成两个阶段:先分配只带相同 ``val`` 的空副本并写入映射,
再依次处理原邻接表。这个顺序是环处理的关键,而不只是实现细节。
以三角形 ``1 -> 2 -> 3 -> 1`` 为例:
.. list-table::
:header-rows: 1
* - 当前调用
- 映射变化
- 邻居处理
* - ``clone(1)``
- 先登记 ``1 -> copy1``
- 递归到 ``2``
* - ``clone(2)``
- 先登记 ``2 -> copy2``
- 遇到 ``1`` 时直接取得 ``copy1``,再继续 ``3``
* - ``clone(3)``
- 先登记 ``3 -> copy3``
- 遇到 ``1``、``2`` 都复用已有副本
如果登记发生在递归邻居之后,从 ``2`` 回到 ``1`` 时映射中还没有 ``1``,递归无法终止。现在每个节点首次
出现时创建一次,后续出现立即返回同一指针,既是访问标记,也是共享副本查询。
边与邻接顺序怎样恢复
~~~~~~~~~~~~~~~~~~~~
对原节点邻接表中的每个 ``originalNeighbor``,递归返回其唯一副本,再追加到当前 ``copy->neighbors``。
因此每条原邻接项产生一条对应的副本邻接项;遍历顺序与原表相同,共享邻居通过映射落到同一对象。无向边
会在两个端点的邻接表中各处理一次,这正是输入表示中的两条邻接记录,不应额外去重。
显式队列替代方案
~~~~~~~~~~~~~~~~
``cloneWithBfs`` 把递归帧换成队列。节点第一次作为邻居被发现时,立即创建副本、登记映射并把原节点入队;
无论邻居是新发现还是已有,随后都把 ``copies[originalNeighbor]`` 接到当前副本的邻接表。这里“必要时创建”
必须先于“建立当前边”,否则新邻居还没有可连接的副本。
BFS 与 DFS 产生的对象地址和访问顺序不同,但都遵守同一映射不变量,复制后的图结构等价。BFS 避免递归
深度风险,代价是显式队列;DFS 更贴近“取得邻居副本并返回”的递归定义。公开入口选择 DFS,BFS 作为
遍历机制上的等价替代保留,认知增量在于展示创建状态与待展开状态可以分离。
为什么结果确实是深拷贝
~~~~~~~~~~~~~~~~~~~~~~
每个映射值都由 ``new Node`` 创建,不是原指针;每次追加邻接关系也只追加映射值。由入口可达的每个原节点
都会被遍历并建立映射,图又保证连通,所以整个图都被复制。原节点没有写操作,也不会出现在返回结构中;
修改副本值或邻接表不会改变原图。
复杂度分析
~~~~~~~~~~
每个节点只创建并展开一次,每条邻接表记录只读取和追加一次,时间 ``O(V + E)``。映射使用 ``O(V)``
空间;DFS 递归栈最坏 ``O(V)``,BFS 队列最坏同为 ``O(V)``。新建的副本图属于返回结果,不计工作空间。