克隆图
邻接表 graph 深拷贝,每个 old 结点对应新 clone。
邻接表 graph 深拷贝,每个 old 结点对应新 clone。
当前节点的合法邻居是谁，访问标记何时写入？
哈希 old→clone;DFS/BFS 复制邻居并连边。
先说结论：这道题到底解决什么
怎样从“邻接表 graph 深拷贝,每个 old 结点对应新 clone。”推导出 图 DFS · 克隆，并证明每次状态变化都不会漏掉答案？
中心结论：哈希 old→clone;DFS/BFS 复制邻居并连边。
- 1.暴力方案在哪里重复计算，为什么仍然是正确基线？
- 2.当前节点的合法邻居是谁，访问标记何时写入？
- 3.不变量“在任意时刻,只要 old 节点出现在 cloneMap 中,它就已经拥有唯一对应的 clone 节点;之后任何地方再遇到这个 old 节点,都必须复用这个 clone。”为什么能保证算法安全前进？
完整题目与题意拆解
邻接表 graph 深拷贝,每个 old 结点对应新 clone。
在本站主例中，邻接表 graph 深拷贝,每个 old 结点对应新 clone。
算法最终需要得到或观察：结构相同的新图。
- • 输入：邻接表 graph 深拷贝,每个 old 结点对应新 clone。
- • 机器需要维护：cloneMap、访问栈。
- • 最终可观察结果：结构相同的新图。
先看清算法到底要维护什么
先建立输入、目标、输出和第一批状态，不急着进入模板。
克隆图:每个结点复制一份,边保持一致
第一层方案：暴力做法
重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。
暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。
重复工作究竟发生在哪里
把重复读取或重复搜索的区域明确标出，再决定优化必须保存什么。
克隆图:每个结点复制一份,边保持一致
整体地图：先做什么，再做什么
- 1建模把输入翻译成“图搜索前线”，明确答案需要观察什么。
- 2状态只维护 cloneMap、访问栈。
- 3转移每一步按照 哈希 old→clone;DFS/BFS 复制邻居并连边。
- 4收尾读取 结构相同的新图。，并复核边界与复杂度。
图搜索前线：核心概念
先把题目对象翻译成节点和边，再选择 BFS 或 DFS。
这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：cloneMap、访问栈。
- • 在任意时刻,只要 old 节点出现在 cloneMap 中,它就已经拥有唯一对应的 clone 节点;之后任何地方再遇到这个 old 节点,都必须复用这个 clone。
建立“图搜索前线”心智模型
用主例建立核心状态，先预测下一步，再公开正确分支和理由。
克隆图:每个结点复制一份,边保持一致
核心机制：状态如何一步步变化
哈希 old→clone;DFS/BFS 复制邻居并连边。
执行过程中持续维护：cloneMap、访问栈。
正确性依赖以下不变量：在任意时刻,只要 old 节点出现在 cloneMap 中,它就已经拥有唯一对应的 clone 节点;之后任何地方再遇到这个 old 节点,都必须复用这个 clone。
面试时可以压缩为：DFS:查 map 命中则复用;否则 new clone 并立刻写入 map,再递归邻居并 append。时间 O(V+E),空间 O(V)。
落到当前题，执行机制可以压缩为：哈希 old→clone;DFS/BFS 复制邻居并连边。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。
一次状态转移为什么成立
集中观察一次选择、计算和状态写回，让变量变化与原因同时出现。
创建 clone(1)
正确性证明：为什么不会漏答案
初始化：算法开始时，全部合法候选仍在状态表示范围内；在任意时刻,只要 old 节点出现在 cloneMap 中,它就已经拥有唯一对应的 clone 节点;之后任何地方再遇到这个 old 节点,都必须复用这个 clone。
保持：执行“哈希 old→clone;DFS/BFS 复制邻居并连边。”时，只删除已经能证明不可能的候选，并把新信息写回 cloneMap、访问栈。
终止：没有待处理状态或达到命中条件时，当前可观察结果就是“结构相同的新图。”。
完整执行过程
- 1题目与输入邻接表 graph 深拷贝,每个 old 结点对应新 clone。 因为：哈希 old→clone;DFS/BFS 复制邻居并连边。
- 2哈希 map: oldId → cloneId遇结点先查 map。 因为：避免重复克隆与死循环。
- 3克隆结点 1 → 11复制结点值。 因为：再递归克隆邻居并连边。
- 4克隆结点 2 → 12复制结点值。 因为：再递归克隆邻居并连边。
- 5克隆结点 3 → 13复制结点值。 因为：再递归克隆邻居并连边。
- 6深拷贝图完成map 中所有结点已复制。 因为：O(V+E) DFS + map。
- 7哈希 map: oldId → cloneId遇结点先查 map。 因为：避免重复克隆与死循环。
- 8收尾与复杂度结构相同的新图。 因为：时间 O(V + E) · 空间 O(V)。哈希 old→clone;DFS/BFS 复制邻居并连边。
从输入完整走到可观察结果
从主例第一帧运行到答案，时间轴始终显示当前状态、因果解释和下一步。
克隆图:每个结点复制一份,边保持一致
把动画和 Go 代码逐行对应
代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。
让每个动作都落到 Go 分支
重新执行关键分支，只显示当前代码附近窗口，并说明这行为什么在此刻运行。
克隆图:每个结点复制一份,边保持一致
完整 Go 提交代码与最小测试
func cloneGraph(node *Node) *Node {
if node == nil { return nil }
copied := map[*Node]*Node{}
var clone func(*Node) *Node
clone = func(current *Node) *Node {
if saved, ok := copied[current]; ok { return saved }
next := &Node{Val: current.Val}
copied[current] = next
for _, neighbor := range current.Neighbors {
next.Neighbors = append(next.Neighbors, clone(neighbor))
}
return next
}
return clone(node)
}func main() {
// 1. 主例
// 输入：mode="clone-graph", numCourses=4
// 期望：结构相同的新图。
//
// 2. 失败 / 未命中
// 检查：没有 map → 环路 dfs 会无限递归。
//
// 3. 边界
// 空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
//
// 4. 迁移
// LC138 复制链表；LC200 岛屿
}正确性与复杂度
执行过程中只保留仍可能影响答案的状态。哈希 old→clone;DFS/BFS 复制邻居并连边。
额外状态主要用于维护：cloneMap、访问栈。
- • 在任意时刻,只要 old 节点出现在 cloneMap 中,它就已经拥有唯一对应的 clone 节点;之后任何地方再遇到这个 old 节点,都必须复用这个 clone。
最容易写错的地方
没有 map → 环路 dfs 会无限递归。
先 dfs(nei) 后写 map → 环再次回到 cur 时找不到登记,同样无限递归。
只复制节点不复制 neighbors → 新图变成一堆孤立节点。
必须额外检查空输入、单元素、未命中或不可达情况，以及恰好落在边界的输入。
最后复盘：带走逻辑链
- 1题意邻接表 graph 深拷贝,每个 old 结点对应新 clone。
- 2重复重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。
- 3优化哈希 old→clone;DFS/BFS 复制邻居并连边。
- 4证明在任意时刻,只要 old 节点出现在 cloneMap 中,它就已经拥有唯一对应的 clone 节点;之后任何地方再遇到这个 old 节点,都必须复用这个 clone。
- 5复杂度时间 O(V + E)，空间 O(V)
- • LC138 复制链表
- • LC200 岛屿