LeetCode 题解工作台
克隆图
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝 （克隆）。 图中的每个节点都包含它的值 val （ int ） 和其邻居的列表（ list[Node] ）。 class Node { public int val; public List neighbors; } 测试用例格式： 简单起…
4
题型
7
代码语言
3
相关题
当前训练重点
中等 · 图·DFS·traversal
答案摘要
我们用一个哈希表 记录原图中的每个节点和它的拷贝节点之间的对应关系，然后进行深度优先搜索。 我们定义函数 ，它的功能是返回 节点的拷贝节点。 的过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
class Node {
public int val;
public List<Node> neighbors;
}
测试用例格式：
简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。
邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。
示例 1：
输入：adjList = [[2,4],[1,3],[2,4],[1,3]] 输出：[[2,4],[1,3],[2,4],[1,3]] 解释： 图中有 4 个节点。 节点 1 的值是 1，它有两个邻居：节点 2 和 4 。 节点 2 的值是 2，它有两个邻居：节点 1 和 3 。 节点 3 的值是 3，它有两个邻居：节点 2 和 4 。 节点 4 的值是 4，它有两个邻居：节点 1 和 3 。
示例 2：
输入：adjList = [[]] 输出：[[]] 解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。
示例 3：
输入：adjList = [] 输出：[] 解释：这个图是空的，它不含任何节点。
提示：
- 这张图中的节点数在
[0, 100]之间。 1 <= Node.val <= 100- 每个节点值
Node.val都是唯一的， - 图中没有重复的边，也没有自环。
- 图是连通图，你可以从给定节点访问到所有节点。
解题思路
方法一：哈希表 + DFS
我们用一个哈希表 记录原图中的每个节点和它的拷贝节点之间的对应关系，然后进行深度优先搜索。
我们定义函数 ，它的功能是返回 节点的拷贝节点。 的过程如下：
- 如果 是 ，那么 的返回值是 。
- 如果 在 中，那么 的返回值是 。
- 否则我们创建一个新的节点 ，并将 的值设为 ，然后遍历 的所有邻居节点 ，并将 的邻居节点列表中加入 。
- 最后返回 。
在主函数中，我们返回 。
时间复杂度 ，空间复杂度 。其中 是节点的数量。
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
from typing import Optional
class Solution:
def cloneGraph(self, node: Optional["Node"]) -> Optional["Node"]:
def dfs(node):
if node is None:
return None
if node in g:
return g[node]
cloned = Node(node.val)
g[node] = cloned
for nxt in node.neighbors:
cloned.neighbors.append(dfs(nxt))
return cloned
g = defaultdict()
return dfs(node)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you understand the importance of using a hash table to store visited nodes during graph traversal?
- question_mark
Can you describe how to handle cycles when cloning a graph using DFS?
- question_mark
Will you explain how the BFS approach can be an alternative to DFS for this problem?
常见陷阱
外企场景- error
Not using a hash table to track cloned nodes, leading to cycles and duplicate clones.
- error
Forgetting to handle empty graphs (edge cases with no nodes).
- error
Mismanaging neighbor lists, potentially losing node connections during cloning.
进阶变体
外企场景- arrow_right_alt
How would you handle cloning a graph with multiple disconnected components?
- arrow_right_alt
Can you modify the algorithm to clone a directed graph?
- arrow_right_alt
What changes would be necessary to clone the graph while maintaining node reference identities (not deep copying)?