LeetCode 133中等图 · DFS/BFS
克隆图 图解题解
这道题到底在问什么
深拷贝一个无向连通图，每个节点有 val 和 neighbors。
- 输入
- 四个节点的无向图
- 输出
- 结构相同的新图
最优解：一步一步想明白
- 3关键不是背模板，而是看懂为什么这题适合图 · DFS/BFS。
- 4深拷贝整张图：从入口 A 开始 DFS。先克隆 A，存哈希表 map[A]=A'(原节点 → 克隆节点)。
- 5沿边 A→B：第一次见 B → 递归克隆 B，map[B]=B'，把 B' 接到 A' 的邻居表。
- 6B 的邻居里 A 已在 map → 直接取 A' 接边、不重复克隆；沿 B→C 递归克隆 C。
- 7沿 C→D：第一次见 D → 递归克隆 D，map[D]=D'。
- 8关键帧：沿 D→A，但 A 已在 map 里 → 直接取 A' 接边，不再递归。哈希表挡住了环 —— 否则 A→B→C→D→A→… 会无限递归。
- 9每个节点只克隆一次、每条边都接到对应的克隆节点，返回入口的克隆 A'。时间 O(V+E)、空间 O(V)。
- 12把这句话记住，下次遇到同类题，就能更快选出方向。
⚠️ 容易写错的地方
✗ 错：不记录已克隆节点
✓ 对：用哈希表避免环里无限递归
图有环，不能像树一样裸递归
✗ 错：只按样例推代码
✓ 对：先写清状态含义和边界条件
样例太少，隐藏用例专打边界
✗ 错：变量名和动画不一致
✓ 对：代码变量沿用动画里的核心名字
学习时最怕脑内维护两套概念
完整代码（Python / C++ / Java）
Python
class Solution:
def cloneGraph(self, node):
if not node: return None
mp = {}
def dfs(cur):
if cur in mp: return mp[cur] # 已克隆，直接返回(挡环)
copy = Node(cur.val)
mp[cur] = copy # 先登记，再递归邻居
for nei in cur.neighbors:
copy.neighbors.append(dfs(nei))
return copy
return dfs(node)C++
class Solution {
public:
unordered_map<Node*, Node*> mp;
Node* cloneGraph(Node* node) {
if (!node) return nullptr;
if (mp.count(node)) return mp[node]; // 已克隆，直接返回
Node* copy = new Node(node->val);
mp[node] = copy; // 先登记
for (Node* nei : node->neighbors)
copy->neighbors.push_back(cloneGraph(nei));
return copy;
}
};Java
class Solution {
Map<Node, Node> mp = new HashMap<>();
public Node cloneGraph(Node node) {
if (node == null) return null;
if (mp.containsKey(node)) return mp.get(node); // 已克隆
Node copy = new Node(node.val);
mp.put(node, copy); // 先登记
for (Node nei : node.neighbors)
copy.neighbors.add(cloneGraph(nei));
return copy;
}
}套路模板 · 图 · DFS/BFS
# 图 · DFS/BFS 通用检查表
# 1. 定义状态/指针/容器
# 2. 每轮只做一个清晰动作
# 3. 更新答案并处理边界复杂度
时间复杂度
O(V+E)
每个核心状态按算法要求处理固定次数
空间复杂度
O(V)
只保存必要的辅助结构或递归栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 克隆图 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么必须用哈希表？+
图可能有环、节点被多个邻居指向；map 保证每个原节点只克隆一次、重复遇到返回同一克隆，避免死循环。
DFS 和 BFS 都行吗？+
都行。DFS 递归、BFS 用队列；关键都是 map 去重。
复杂度？+
O(V+E)：每个节点和每条边各处理一次。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。