题目描述
深拷贝一个无向连通图，每个节点有 val 和 neighbors。
输入 = 四个节点的无向图
输出 = 结构相同的新图
思路解析
关键不是背模板，而是看懂为什么这题适合图 · DFS/BFS。
1. 先克隆入口节点 A：先克隆入口节点 A
2. 把 A 映射到 A'：把 A 映射到 A'
3. 遍历 A 的邻居 B、D：遍历 A 的邻居 B、D
4. 第一次见 B，递归克隆 B：第一次见 B，递归克隆 B
5. B 的邻居里又看到 A，直接用映射表：B 的邻居里又看到 A，直接用映射表
6. 继续克隆 C、D：继续克隆 C、D
7. 每条边都连接到新节点：每条边都连接到新节点
8. 返回入口的新节点：返回入口的新节点
把这句话记住，下次遇到同类题，就能更快选出方向。
用一个小问题检查自己是不是真的懂了。
参考代码（Python）
Python
1class Solution:
2 def cloneGraph(self, node):
3 if not node:
4 return None
5 mp = {}
6 def dfs(cur):
7 if cur in mp:
8 return mp[cur]
9 copy = Node(cur.val)
10 mp[cur] = copy
11 for nei in cur.neighbors:
12 copy.neighbors.append(dfs(nei))
13 return copy
14 return dfs(node)复杂度分析
- 时间复杂度：O(V+E) —— 每个核心状态按算法要求处理固定次数
- 空间复杂度：O(V) —— 只保存必要的辅助结构或递归栈
套路模板
模板不是死背，而是提醒你写代码前先把状态、转移和边界排好。
Python
1# 图 · DFS/BFS 通用检查表
2# 1. 定义状态/指针/容器
3# 2. 每轮只做一个清晰动作
4# 3. 更新答案并处理边界易错点
- 错误写法：不记录已克隆节点 → 正确写法：用哈希表避免环里无限递归（图有环，不能像树一样裸递归）
- 错误写法：只按样例推代码 → 正确写法：先写清状态含义和边界条件（样例太少，隐藏用例专打边界）
- 错误写法：变量名和动画不一致 → 正确写法：代码变量沿用动画里的核心名字（学习时最怕脑内维护两套概念）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。