克隆图 · 为什么 old → clone 映射表才是本题核心
DFS · HashMap 防环给定图中任意一个节点,返回这张无向连通图的深拷贝。 新图节点必须是全新对象,但结构、节点值与邻居关系都要与旧图一致。 难点在于图有环、有共享邻居,所以必须维护一张cloneMap: old → clone。
这题不是复制一个节点,而是复制一整张关系网
题目只给你图里的一个入口节点 node。 但这个 node 不是孤立的,它通过 neighbors 连接着其他节点; 其他节点又继续连接更多节点。所以这题真正要做的是:
- 从入口 node 出发,沿着 neighbors 把整张旧图走一遍;
- 为旧图里的每个节点创建一个全新的 clone 节点;
- 再把 clone 节点之间的邻居关系也一模一样地连起来;
- 最后返回新图里的入口节点 cloneNode。
三个概念先讲清楚
完全没接触过图也没关系,先把这三个词弄懂,后面就顺了。
什么是连通?
连通的意思是:从任意一个节点出发,只要沿着 neighbors 一直走, 最终可以走到图里的所有节点。
比如从节点 1 出发,可以走到 2 和 4;从 2 又可以走到 3;所以 1、2、3、4 都能被访问到。 这就是为什么题目只给你一个 node,你仍然能克隆整张图。
什么是深拷贝?
深拷贝不是把旧节点直接拿来用。旧图里的节点 1,和新图里的节点 1', 值可以一样、邻居关系也可以一样,但它们必须是两个不同的对象。
也就是说:old1 != clone1。
clone1.Neighbors = old1.Neighborsclone1.Neighbors = append(clone1.Neighbors, clone2)什么是 neighbors?
每个节点都有一个 Neighbors 列表, 表示它直接连接的节点。
如果 1.neighbors = [2, 4], 说明节点 1 直接连接节点 2 和节点 4。
怎么把这道题建模成代码?
Step A · 节点 Node
type Node struct {
Val int
Neighbors []*Node
}Val 是节点编号, Neighbors 是它直接连接的邻居节点列表。
Step B · 边 Edge
如果 1 的 neighbors 里有 2,就表示 1 和 2 之间有一条边。
无向图里,这条边可以从 1 走到 2,也可以从 2 走回 1。
Step C · 入口 node
题目没有给你完整数组,也没有给你所有节点列表。它只给你一个入口节点 node。
你需要从这个入口开始,通过 DFS 或 BFS 沿着 neighbors 探索,边走边发现整张图。
Step D · 状态 cloneMap
克隆图时,我们需要同时记住两件事:
- 旧节点有没有被克隆过?
- 如果克隆过,它对应的新节点是谁?
所以需要 cloneMap[oldNode] = clonedNode:
整个算法只围绕 4 个动作
进入一个旧节点 cur 后,先看它是否已经克隆过。如果 cloneMap[cur] 存在,直接返回已有 clone,避免重复克隆和无限递归。
如果 cur 没有被克隆过,创建一个新节点 clone,值等于 cur.Val。
遍历 cur.Neighbors,对每个邻居调用 dfs(neighbor),先把邻居那一侧的 clone 拿到手。
把 dfs(neighbor) 返回的 clone append 到 clone.Neighbors,新图这条边才算连好。
为什么必须有 cloneMap?
图与树不同: 图可能有环,也可能多个节点共享同一个邻居。 如果你只用“裸 DFS + 不停 new Node”，会立刻出两个 bug:
old 1 → old 2 → old 1 → old 2 … 没有 map 就无法判断“我已经在克隆这个节点了”， 调用栈瞬间爆掉。
如果 old 2 和 old 4 都把 old 1 当邻居,各自创建一个新 clone 1, 新图里就出现了两个不同的 1 —— 结构错了。
每次进入一个 old 节点,先查 cloneMap:已存在 → 直接复用,不重建也不再递归; 不存在 → 创建 clone 并立刻写入 map,然后再递归邻居。 这条规则同时解决“环”和“共享邻居”。
测试样例 · 切换后整段动画会重算
旧图 old graph
只读 · 不会被修改cloneMap · old → clone
0 条记录还没有 dfs 进入过任何节点
新图 cloned graph
0 个 clone · 0 条边等待第一次 visit-create 帧
题目目标 · 复制整张图,不是复制一个点
题目只给你图里的一个入口节点 node。但 node 不是孤立的,它通过 neighbors 连着别的节点,别的节点又连着更多节点。所以真正要做的是:从入口 old 1 出发,沿 neighbors 把整张旧图走一遍,为每个旧节点造一个全新的 clone,再把 clone 之间的邻居关系也一模一样地连起来,最后返回新图入口 clone 1。
为什么这一步是对的
深拷贝意味着不能把旧引用塞进新结构,所有 *Node 必须是新分配的。
DFS 调用栈
代码同步 · Go
题目1func cloneGraph(node *Node) *Node {2 if node == nil {3 return nil4 }56 cloneMap := map[*Node]*Node{}78 var dfs func(*Node) *Node9 dfs = func(cur *Node) *Node {10 if cloned, ok := cloneMap[cur]; ok {11 return cloned12 }1314 clone := &Node{Val: cur.Val}15 cloneMap[cur] = clone1617 for _, nei := range cur.Neighbors {18 clone.Neighbors = append(clone.Neighbors, dfs(nei))19 }2021 return clone22 }2324 return dfs(node)25}
剧本时间线 · 共 31 步
正确性不变量
在任意时刻, 只要 old 节点出现在 cloneMap 中,它就已经拥有唯一对应的 clone 节点。 之后任何地方再遇到这个 old 节点,都必须复用这个 clone。
这条不变量同时给出了正确性(无重复节点、邻居关系准确)与复杂度上界 (每个节点构造 1 次 · 每条边 append 1 次)。
错误做法 vs 正确做法
错误做法
- ✗ 每次遇到邻居就 new Node — 没有 map,同一旧节点被反复 new 出多个新对象,新图里出现多个同值不同实例的“假冒节点”。
- ✗ 没有先写入 map 就递归邻居 — 在 cloneMap[cur] = clone 之前调用 dfs(nei),环路上的递归会一路杀回 cur, 而 cur 还没进 map → 无限递归。
- ✗ 只复制节点,忘记复制 neighbors — clone 出来了,但 clone.Neighbors 是空切片。 新图只是一堆孤立的节点,没有边。
正确做法
- 先查 map:if cloned, ok := cloneMap[cur]; ok 就立刻 return。
- 不存在 → 创建 clone 并立刻写入 map:cloneMap[cur] = clone。这一步必须在递归之前。
- 再递归复制邻居并连边:clone.Neighbors = append(clone.Neighbors, dfs(nei))。 dfs(nei) 的返回值就是 clone 邻居 —— 它要么是新创建的,要么是 map 命中复用的。
面试 · 一段话讲清楚
这题是图的深拷贝。 难点在于图可能有环,所以不能直接递归 new 节点。 我用一个哈希表记录 old node → cloned node 的映射。 DFS 时先判断当前节点是否已经克隆过,如果克隆过直接返回; 否则创建新节点放入 map,然后递归克隆所有邻居,并把克隆后的邻居加入当前 clone 的 neighbors。 每个点和每条边只处理一次,所以时间 O(V+E),空间 O(V)。
常见误区
- ✗ 空间复杂度写成 O(1) — 忽略了 cloneMap 与递归栈,正确是 O(V)。
- ✗ 时间写成 O(n) 而不说 n 是什么 — 准确表述是 O(V + E)。
- ✗ 忘记空图保护 — node == nil 要直接返回 nil。
- ✗ 用值作 map key 是可以的(本题节点值唯一),但更通用的是用 *Node 指针作 key。