第8章｜图与并查集

Unit 04 · LeetCode #133 克隆图

仅本次页面有效

U04

Identity Map + Deep CopyCreate → Register → Reuse → Connect

深拷贝不是“画一张长得一样的图”，
而是建立一个完全独立的节点世界。

每个原节点必须只创建一个副本；副本的邻居必须指向副本世界。图中存在环，因此必须先把 original → clone 写入映射，再继续复制邻居。

检测到上次学习现场阶段、动画步、问题、代码、槽位、迁移脚手架、编辑器高度与滚动位置均可恢复。

给定一个连通无向图中某个节点的引用，返回该图的深拷贝。每个节点包含整数值 val 和邻居列表 neighbors。

示例 1 输入：adjList = [[2,4],[1,3],[2,4],[1,3]] 输出：[[2,4],[1,3],[2,4],[1,3]] 示例 2 输入：adjList = [[]] 输出：[[]] 示例 3 输入：adjList = [] 输出：[]

节点数量：0 到 100 1 ≤ Node.val ≤ 100 节点值互不相同没有重复边和自环图连通，可从给定节点访问全部节点 class Solution: def cloneGraph(self, node: Optional['Node']) -> Optional['Node']: ...

本实验采用 DFS + 哈希映射，重点不是递归语法，而是副本身份与引用关系。

original

原图中的节点对象，是映射表的键。

clone

全新的节点对象，值相同但身份不同。

copies

保证每个原节点只对应一个副本，同时避免环中的重复递归。

Shallow Copy

只复制外层对象，内部引用仍可能指向原对象。

Deep Copy

节点和所有可达引用都指向全新的副本世界。

Identity

对象身份由内存中的节点对象决定，不由 val 单独决定。

Register Before Recurse

先登记副本，再复制邻居；遇到回边时可直接复用。

克隆图实验步骤 1

图的深拷贝 = 节点身份映射 + 图遍历 + 副本边重建。每个原节点只创建一次；遇到已登记节点时复用副本；副本的所有邻居必须位于副本世界。

Graph Model节点对象与 neighbors 引用构成图

Identity Mapcopies[original] = clone

Order先创建并登记，再递归邻居

Reuse已登记节点直接返回已有副本

Deep Copy副本边只能连接副本节点

Complexity时间 O(V+E)，空间 O(V)

完成后停留在当前页面

不会自动跳题。可以返回任意阶段重播映射与递归过程，或继续修改迁移代码。