LeetCode 133克隆图 | 哈希表存储原节点到新节点的映射引言克隆图Clone Graph是 LeetCode 第 133 题难度为 Medium。题目要求深度拷贝一个无向图返回一个新的图的节点其中新图是原图的完全复制。这道题的核心挑战在于如何正确处理图中可能存在的环——如果使用简单的深度优先搜索可能会在环上陷入无限循环。哈希表在这里的作用是建立原图节点到新图节点的映射。通过在遍历之前就创建新节点并将映射关系存储在哈希表中我们可以确保每个节点只被创建一次避免重复创建导致的内存浪费和可能的死循环。这种先记录再连接的策略是解决图克隆问题的关键。问题分析题目描述给定无向图的引用节点值从 1 到 n返回该图的深拷贝。图中每个节点包含一个整数值和一个邻居列表。邻居是节点指针数组每个指针指向无向图中其他节点。例如输入adjList [[2,4],[1,3],[2,4],[1,3]] 解释图中有 4 个节点节点 1 连接到 2 和 4节点 2 连接到 1 和 3等等。问题特点这道题的核心挑战是无向图中的环。由于是无向图节点 A 可能是节点 B 的邻居节点 B 也可能是节点 A 的邻居。如果直接使用深度优先搜索而不记录已访问的节点在存在环的情况下会导致无限递归。另一个挑战是邻居关系的复制。在遍历原图时我们需要同时创建新节点并建立邻居关系。但由于图不是树同一个节点可能被多个其他节点引用如何确保所有引用都指向同一个新节点而不是创建多个副本是一个关键问题。图的表示在 LeetCode 中图的节点通常定义如下class Node: def __init__(self, val0, neighborsNone): self.val val self.neighbors neighbors if neighbors else []neighbors 是一个列表包含指向其他节点的引用。在实际测试中节点值是从 1 开始的连续整数。解决方案哈希表深度优先搜索def cloneGraph(node): if not node: return None visited {} def dfs(original): if original in visited: return visited[original] clone Node(original.val) visited[original] clone for neighbor in original.neighbors: clone.neighbors.append(dfs(neighbor)) return clone return dfs(node)这段代码展示了使用哈希表的深度优先搜索解法。哈希表 visited 存储原节点到克隆节点的映射。在 dfs 函数中首先检查当前节点是否已经克隆过即是否在哈希表中如果已克隆直接返回克隆节点避免重复处理。然后创建新的克隆节点并将其存入哈希表。接下来递归克隆所有邻居节点将它们添加到克隆节点的邻居列表中。最后返回克隆节点。迭代版本BFSfrom collections import deque def cloneGraph_bfs(node): if not node: return None visited {node: Node(node.val)} queue deque([node]) while queue: original queue.popleft() for neighbor in original.neighbors: if neighbor not in visited: visited[neighbor] Node(neighbor.val) queue.append(neighbor) visited[original].neighbors.append(visited[neighbor]) return visited[node]BFS 版本使用队列进行层序遍历。初始时将起始节点加入队列并创建其克隆节点。然后不断从队列中取出节点处理其所有邻居对于未访问过的邻居创建克隆节点并加入队列将克隆邻居添加到当前克隆节点的邻居列表中。算法详解为什么需要哈希表哈希表的核心作用是建立原节点到克隆节点的映射。这个映射有两个重要用途第一避免重复克隆同一个节点第二确保所有对新节点的引用都指向同一个克隆对象。考虑图中存在环的情况1 - 2 - 3 - 1。如果不使用哈希表当我们从节点 1 出发克隆节点 1然后克隆节点 2再克隆节点 3当我们尝试克隆节点 1 的邻居时我们会再次克隆节点 1而不是使用之前创建的克隆。这会导致创建多个节点 1 的副本而且邻居关系不正确可能形成多个不相连的副本。使用哈希表后当我们第二次访问节点 1 时发现它已经在哈希表中直接返回之前创建的克隆节点确保了整个图结构的正确性。递归的终止条件递归终止条件有两个节点为空返回 None和节点已被克隆返回已克隆的节点。第二个条件既是正确性的保证也是避免无限递归的关键。当节点已被克隆时我们不再递归处理它的邻居而是直接返回已创建的克隆节点。这确保了每个节点只被处理一次。邻居关系的建立时机在递归方法中邻居关系是在递归返回时建立的。当我们递归调用 dfs(neighbor) 时会返回 neighbor 的克隆节点我们将它添加到当前节点的克隆的邻居列表中。在 BFS 方法中邻居关系是在遍历队列时建立的。每次从队列中取出一个节点我们处理它的所有邻居将未访问过的邻居加入队列并将邻居的克隆添加到当前节点克隆的邻居列表中。代码实现Python 实现class Node: def __init__(self, val0, neighborsNone): self.val val self.neighbors neighbors if neighbors else [] def cloneGraph(node): if not node: return None visited {} def dfs(original): if original in visited: return visited[original] clone Node(original.val) visited[original] clone for neighbor in original.neighbors: clone.neighbors.append(dfs(neighbor)) return clone return dfs(node)Java 实现public Node cloneGraph(Node node) { if (node null) { return null; } MapNode, Node visited new HashMap(); return dfs(node, visited); } private Node dfs(Node node, MapNode, Node visited) { if (visited.containsKey(node)) { return visited.get(node); } Node clone new Node(node.val); visited.put(node, clone); for (Node neighbor : node.neighbors) { clone.neighbors.add(dfs(neighbor, visited)); } return clone; }复杂度分析时间复杂度时间复杂度为 O(n m)其中 n 是节点数m 是边数。每个节点被访问一次处理一次每条边被访问一次在处理节点时被遍历。哈希表操作是 O(1) 的平均时间所以总时间复杂度是线性的。空间复杂度空间复杂度为 O(n)用于存储哈希表n 个节点的映射和递归调用栈最深可达 n当图是链表结构时。在 BFS 版本中空间复杂度为 O(n)用于存储哈希表和队列。边界情况处理空图当输入节点为空时返回空。代码正确处理了这种情况。单节点无邻居当图只有一个节点且没有邻居时如 [[]]节点 1 连接到空列表算法仍然正确创建克隆节点递归调用处理空邻居列表返回只有一个节点的新图。多节点有环这是最常见的测试场景。算法正确处理有环的图确保每个节点只被克隆一次。完全图完全图是每个节点都与其他所有节点相连的图。对于 n 个节点的完全图边数为 n*(n-1)/2。算法正确处理这种情况每个节点的邻居都被正确复制。变种问题克隆带权图如果图的边有权重我们需要存储每个邻居的权重。可以将邻居列表从 Node 列表改为 (Node, weight) 元组列表或者使用额外的边类。克隆有向图如果有向图的边是有方向的算法同样适用因为邻居关系是单向的。只需要按原方向复制邻居关系即可。克隆多重图如果图中两个节点之间可能有多条边算法需要稍作修改邻居列表中可能包含重复的邻居需要在克隆时处理这种重复。测试用例def build_graph(adj_list): if not adj_list: return None nodes [None] [Node(i) for i in range(1, len(adj_list))] for i, neighbors in enumerate(adj_list): if i 0: nodes[i].neighbors [nodes[neighbor] for neighbor in neighbors] return nodes[1] if len(adj_list) 1 else None def test_clone_graph(): graph1 build_graph([[2, 4], [1, 3], [2, 4], [1, 3]]) cloned1 cloneGraph(graph1) assert cloned1.val 1 assert len(cloned1.neighbors) 2 assert all(n.val in [2, 4] for n in cloned1.neighbors) graph2 build_graph([[]]) cloned2 cloneGraph(graph2) assert cloned2.val 1 assert len(cloned2.neighbors) 0 graph3 build_graph([[2], [3], [4], []]) cloned3 cloneGraph(graph3) assert cloned3.val 1 assert len(cloned3.neighbors) 1 assert cloned3.neighbors[0].val 2 print(所有测试用例通过)实际应用场景图的克隆在现实中有很多应用。在版本控制系统中分支可以看作是对原图提交历史的克隆每个提交是一个节点边表示提交之间的依赖关系。在社交网络分析中可能需要克隆网络结构来分析不同的场景。在游戏开发中场景图Scene Graph的克隆用于实现撤销/重做功能或保存/加载功能。图克隆问题展示了一个重要的算法设计原则当处理可能包含环的递归结构时必须记录已访问的节点避免无限循环。哈希表是实现这一原则的常用工具。总结克隆图是哈希表在图论问题中应用的经典案例。通过建立原节点到克隆节点的映射我们不仅避免了重复克隆还确保了所有邻居引用都指向同一个克隆对象。这是解决图克隆问题的标准范式。在面试中克隆图问题经常被问到因为它考察了对图结构、哈希表和递归/迭代算法的综合理解。希望通过本文的讲解读者能够深入理解图克隆的哈希表方法并将其推广到其他涉及环结构的递归问题中。
LeetCode 133：克隆图 | 哈希表存储原节点到新节点的映射
LeetCode 133克隆图 | 哈希表存储原节点到新节点的映射引言克隆图Clone Graph是 LeetCode 第 133 题难度为 Medium。题目要求深度拷贝一个无向图返回一个新的图的节点其中新图是原图的完全复制。这道题的核心挑战在于如何正确处理图中可能存在的环——如果使用简单的深度优先搜索可能会在环上陷入无限循环。哈希表在这里的作用是建立原图节点到新图节点的映射。通过在遍历之前就创建新节点并将映射关系存储在哈希表中我们可以确保每个节点只被创建一次避免重复创建导致的内存浪费和可能的死循环。这种先记录再连接的策略是解决图克隆问题的关键。问题分析题目描述给定无向图的引用节点值从 1 到 n返回该图的深拷贝。图中每个节点包含一个整数值和一个邻居列表。邻居是节点指针数组每个指针指向无向图中其他节点。例如输入adjList [[2,4],[1,3],[2,4],[1,3]] 解释图中有 4 个节点节点 1 连接到 2 和 4节点 2 连接到 1 和 3等等。问题特点这道题的核心挑战是无向图中的环。由于是无向图节点 A 可能是节点 B 的邻居节点 B 也可能是节点 A 的邻居。如果直接使用深度优先搜索而不记录已访问的节点在存在环的情况下会导致无限递归。另一个挑战是邻居关系的复制。在遍历原图时我们需要同时创建新节点并建立邻居关系。但由于图不是树同一个节点可能被多个其他节点引用如何确保所有引用都指向同一个新节点而不是创建多个副本是一个关键问题。图的表示在 LeetCode 中图的节点通常定义如下class Node: def __init__(self, val0, neighborsNone): self.val val self.neighbors neighbors if neighbors else []neighbors 是一个列表包含指向其他节点的引用。在实际测试中节点值是从 1 开始的连续整数。解决方案哈希表深度优先搜索def cloneGraph(node): if not node: return None visited {} def dfs(original): if original in visited: return visited[original] clone Node(original.val) visited[original] clone for neighbor in original.neighbors: clone.neighbors.append(dfs(neighbor)) return clone return dfs(node)这段代码展示了使用哈希表的深度优先搜索解法。哈希表 visited 存储原节点到克隆节点的映射。在 dfs 函数中首先检查当前节点是否已经克隆过即是否在哈希表中如果已克隆直接返回克隆节点避免重复处理。然后创建新的克隆节点并将其存入哈希表。接下来递归克隆所有邻居节点将它们添加到克隆节点的邻居列表中。最后返回克隆节点。迭代版本BFSfrom collections import deque def cloneGraph_bfs(node): if not node: return None visited {node: Node(node.val)} queue deque([node]) while queue: original queue.popleft() for neighbor in original.neighbors: if neighbor not in visited: visited[neighbor] Node(neighbor.val) queue.append(neighbor) visited[original].neighbors.append(visited[neighbor]) return visited[node]BFS 版本使用队列进行层序遍历。初始时将起始节点加入队列并创建其克隆节点。然后不断从队列中取出节点处理其所有邻居对于未访问过的邻居创建克隆节点并加入队列将克隆邻居添加到当前克隆节点的邻居列表中。算法详解为什么需要哈希表哈希表的核心作用是建立原节点到克隆节点的映射。这个映射有两个重要用途第一避免重复克隆同一个节点第二确保所有对新节点的引用都指向同一个克隆对象。考虑图中存在环的情况1 - 2 - 3 - 1。如果不使用哈希表当我们从节点 1 出发克隆节点 1然后克隆节点 2再克隆节点 3当我们尝试克隆节点 1 的邻居时我们会再次克隆节点 1而不是使用之前创建的克隆。这会导致创建多个节点 1 的副本而且邻居关系不正确可能形成多个不相连的副本。使用哈希表后当我们第二次访问节点 1 时发现它已经在哈希表中直接返回之前创建的克隆节点确保了整个图结构的正确性。递归的终止条件递归终止条件有两个节点为空返回 None和节点已被克隆返回已克隆的节点。第二个条件既是正确性的保证也是避免无限递归的关键。当节点已被克隆时我们不再递归处理它的邻居而是直接返回已创建的克隆节点。这确保了每个节点只被处理一次。邻居关系的建立时机在递归方法中邻居关系是在递归返回时建立的。当我们递归调用 dfs(neighbor) 时会返回 neighbor 的克隆节点我们将它添加到当前节点的克隆的邻居列表中。在 BFS 方法中邻居关系是在遍历队列时建立的。每次从队列中取出一个节点我们处理它的所有邻居将未访问过的邻居加入队列并将邻居的克隆添加到当前节点克隆的邻居列表中。代码实现Python 实现class Node: def __init__(self, val0, neighborsNone): self.val val self.neighbors neighbors if neighbors else [] def cloneGraph(node): if not node: return None visited {} def dfs(original): if original in visited: return visited[original] clone Node(original.val) visited[original] clone for neighbor in original.neighbors: clone.neighbors.append(dfs(neighbor)) return clone return dfs(node)Java 实现public Node cloneGraph(Node node) { if (node null) { return null; } MapNode, Node visited new HashMap(); return dfs(node, visited); } private Node dfs(Node node, MapNode, Node visited) { if (visited.containsKey(node)) { return visited.get(node); } Node clone new Node(node.val); visited.put(node, clone); for (Node neighbor : node.neighbors) { clone.neighbors.add(dfs(neighbor, visited)); } return clone; }复杂度分析时间复杂度时间复杂度为 O(n m)其中 n 是节点数m 是边数。每个节点被访问一次处理一次每条边被访问一次在处理节点时被遍历。哈希表操作是 O(1) 的平均时间所以总时间复杂度是线性的。空间复杂度空间复杂度为 O(n)用于存储哈希表n 个节点的映射和递归调用栈最深可达 n当图是链表结构时。在 BFS 版本中空间复杂度为 O(n)用于存储哈希表和队列。边界情况处理空图当输入节点为空时返回空。代码正确处理了这种情况。单节点无邻居当图只有一个节点且没有邻居时如 [[]]节点 1 连接到空列表算法仍然正确创建克隆节点递归调用处理空邻居列表返回只有一个节点的新图。多节点有环这是最常见的测试场景。算法正确处理有环的图确保每个节点只被克隆一次。完全图完全图是每个节点都与其他所有节点相连的图。对于 n 个节点的完全图边数为 n*(n-1)/2。算法正确处理这种情况每个节点的邻居都被正确复制。变种问题克隆带权图如果图的边有权重我们需要存储每个邻居的权重。可以将邻居列表从 Node 列表改为 (Node, weight) 元组列表或者使用额外的边类。克隆有向图如果有向图的边是有方向的算法同样适用因为邻居关系是单向的。只需要按原方向复制邻居关系即可。克隆多重图如果图中两个节点之间可能有多条边算法需要稍作修改邻居列表中可能包含重复的邻居需要在克隆时处理这种重复。测试用例def build_graph(adj_list): if not adj_list: return None nodes [None] [Node(i) for i in range(1, len(adj_list))] for i, neighbors in enumerate(adj_list): if i 0: nodes[i].neighbors [nodes[neighbor] for neighbor in neighbors] return nodes[1] if len(adj_list) 1 else None def test_clone_graph(): graph1 build_graph([[2, 4], [1, 3], [2, 4], [1, 3]]) cloned1 cloneGraph(graph1) assert cloned1.val 1 assert len(cloned1.neighbors) 2 assert all(n.val in [2, 4] for n in cloned1.neighbors) graph2 build_graph([[]]) cloned2 cloneGraph(graph2) assert cloned2.val 1 assert len(cloned2.neighbors) 0 graph3 build_graph([[2], [3], [4], []]) cloned3 cloneGraph(graph3) assert cloned3.val 1 assert len(cloned3.neighbors) 1 assert cloned3.neighbors[0].val 2 print(所有测试用例通过)实际应用场景图的克隆在现实中有很多应用。在版本控制系统中分支可以看作是对原图提交历史的克隆每个提交是一个节点边表示提交之间的依赖关系。在社交网络分析中可能需要克隆网络结构来分析不同的场景。在游戏开发中场景图Scene Graph的克隆用于实现撤销/重做功能或保存/加载功能。图克隆问题展示了一个重要的算法设计原则当处理可能包含环的递归结构时必须记录已访问的节点避免无限循环。哈希表是实现这一原则的常用工具。总结克隆图是哈希表在图论问题中应用的经典案例。通过建立原节点到克隆节点的映射我们不仅避免了重复克隆还确保了所有邻居引用都指向同一个克隆对象。这是解决图克隆问题的标准范式。在面试中克隆图问题经常被问到因为它考察了对图结构、哈希表和递归/迭代算法的综合理解。希望通过本文的讲解读者能够深入理解图克隆的哈希表方法并将其推广到其他涉及环结构的递归问题中。
