LeetCode 133中等图 · DFS/BFS
克隆图 图解题解
这道题到底在问什么
从给定节点出发，遍历整张图。每个节点新建一个副本，并用哈希表记住「原节点→克隆节点」的映射，再把克隆节点之间按原图连边。
- 输入
- 6 节点环 + 对角（1-2-3-4-1, 1-3, 5↔1/2, 6↔3/4）
- 输出
- 同构副本图
最优解：一步一步想明白
- 3记住「先查表、没有才新建」这一招，下面每一步都在用它。
- 4原图在这里：6 个节点、若干条边。我们要在右侧逐个建出它们的副本。
- 5访问节点 1：查哈希表 map，里面还没有它 → 新建副本 1'，并写入 map[1]=1'。
- 6节点 1 克隆完成，加入「已克隆」面板。它的邻居稍后入队，依次同样处理。
- 7访问节点 2：查哈希表 map，里面还没有它 → 新建副本 2'，并写入 map[2]=2'。
- 8节点 2 克隆完成，加入「已克隆」面板。它的邻居稍后入队，依次同样处理。
- 9连边：原图里 1—2 相邻，于是在克隆图里把副本 1' 和 2' 也连起来（map 里取出两端的克隆节点）。
- 10访问节点 4：查哈希表 map，里面还没有它 → 新建副本 4'，并写入 map[4]=4'。
- 11节点 4 克隆完成，加入「已克隆」面板。它的邻居稍后入队，依次同样处理。
- 12连边：原图里 1—4 相邻，于是在克隆图里把副本 1' 和 4' 也连起来（map 里取出两端的克隆节点）。
- 13访问节点 3：查哈希表 map，里面还没有它 → 新建副本 3'，并写入 map[3]=3'。
- 14节点 3 克隆完成，加入「已克隆」面板。它的邻居稍后入队，依次同样处理。
- 15连边：原图里 1—3 相邻，于是在克隆图里把副本 1' 和 3' 也连起来（map 里取出两端的克隆节点）。
- 16访问节点 5：查哈希表 map，里面还没有它 → 新建副本 5'，并写入 map[5]=5'。
- 17节点 5 克隆完成，加入「已克隆」面板。它的邻居稍后入队，依次同样处理。
- 18连边：原图里 1—5 相邻，于是在克隆图里把副本 1' 和 5' 也连起来（map 里取出两端的克隆节点）。
- 19连边：原图里 2—3 相邻，于是在克隆图里把副本 2' 和 3' 也连起来（map 里取出两端的克隆节点）。
- 20连边：原图里 2—5 相邻，于是在克隆图里把副本 2' 和 5' 也连起来（map 里取出两端的克隆节点）。
- 21连边：原图里 4—3 相邻，于是在克隆图里把副本 4' 和 3' 也连起来（map 里取出两端的克隆节点）。
- 22访问节点 6：查哈希表 map，里面还没有它 → 新建副本 6'，并写入 map[6]=6'。
- 23节点 6 克隆完成，加入「已克隆」面板。它的邻居稍后入队，依次同样处理。
- 24连边：原图里 4—6 相邻，于是在克隆图里把副本 4' 和 6' 也连起来（map 里取出两端的克隆节点）。
- 25连边：原图里 3—6 相邻，于是在克隆图里把副本 3' 和 6' 也连起来（map 里取出两端的克隆节点）。
- 26全部节点都克隆了、全部边都连上了——右侧面板里 6 个副本就是这张图的深拷贝，返回起点的副本即可。
⚠️ 容易写错的地方
✗ 错：不用哈希表去重
✓ 对：每访问一个节点先查 map，没有才新建
否则环里会无限重复克隆同一节点
✗ 错：克隆了节点忘连边
✓ 对：克隆节点的 neighbors 也要逐条接上
深拷贝必须连同边一起复制
✗ 错：连到原图节点
✓ 对：neighbors 里 push 的是 map[nb] 副本，不是 nb 本体
连错就成了原图的引用，不是深拷贝
完整代码（Python / C++ / Java）
Python
def cloneGraph(node):
if not node: return None
mp = {} # 原节点 -> 克隆节点
q = deque([node])
mp[node] = Node(node.val) # 先克隆起点
while q:
cur = q.popleft()
for nb in cur.neighbors:
if nb not in mp: # 没克隆过才新建
mp[nb] = Node(nb.val)
q.append(nb)
mp[cur].neighbors.append(mp[nb]) # 连克隆边
return mp[node]C++
Node* cloneGraph(Node* node){
if(!node) return nullptr;
unordered_map<Node*,Node*> mp;
queue<Node*> q; q.push(node);
mp[node] = new Node(node->val);
while(!q.empty()){
Node* cur = q.front(); q.pop();
for(Node* nb : cur->neighbors){
if(!mp.count(nb)){
mp[nb] = new Node(nb->val);
q.push(nb);
}
mp[cur]->neighbors.push_back(mp[nb]);
}
}
return mp[node];
}Java
public Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> mp = new HashMap<>();
Queue<Node> q = new LinkedList<>();
q.offer(node);
mp.put(node, new Node(node.val));
while (!q.isEmpty()) {
Node cur = q.poll();
for (Node nb : cur.neighbors) {
if (!mp.containsKey(nb)) {
mp.put(nb, new Node(nb.val));
q.offer(nb);
}
mp.get(cur).neighbors.add(mp.get(nb));
}
}
return mp.get(node);
}复杂度
时间
O(V+E)
每个节点访问一次、每条边处理一次
空间
O(V)
哈希表存 V 个映射 + 队列
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 克隆图 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
DFS 还是 BFS 都能做吗？+
都行。DFS 用递归 + 同一张 map；BFS 用队列 + map。映射表的作用完全一样，只是遍历顺序不同。
为什么不能简单地新建结构后再连边？+
可以分两遍：先建所有副本写满 map，再遍历连边。一遍 BFS 是把「建点」和「连边」合在访问邻居时一起做，更省。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 克隆图 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。