企业官网建设流程全解析

LeetCode 133 克隆图 是一道经典的 图遍历 + 深拷贝 问题。

题目描述

给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。

图中的每个节点包含一个整数值
“val” 和一个邻居列表
“neighbors”。

图中节点数在
“[0, 100]” 之间。

解题思路

由于图可能存在环（比如节点 A 的邻居是 B，B 的邻居又是 A），直接递归或遍历会导致无限循环。因此我们需要一个 哈希表（字典） 来记录原节点 -> 克隆节点的映射关系：

• 如果节点已经克隆过，直接返回克隆节点的引用。
• 如果没克隆过，创建新节点并递归/BFS 克隆其邻居。

方法一：DFS（深度优先搜索，递归）

Definition for a Node.

class Node:
definit(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []

class Solution:
def cloneGraph(self, node: ‘Node’) -> ‘Node’:
if not node:
return None

# 字典：原节点 -> 克隆节点 visited = {} def dfs(cur_node): # 如果已经克隆过，直接返回克隆节点 if cur_node in visited: return visited[cur_node] # 创建新节点（注意：先不克隆邻居，避免递归死循环） clone_node = Node(cur_node.val, []) visited[cur_node] = clone_node # 递归克隆所有邻居 for neighbor in cur_node.neighbors: clone_node.neighbors.append(dfs(neighbor)) return clone_node return dfs(node)

方法二：BFS（广度优先搜索，迭代）

Definition for a Node.

class Node:
definit(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []

from collections import deque

class Solution:
def cloneGraph(self, node: ‘Node’) -> ‘Node’:
if not node:
return None

visited = {} # 克隆起始节点 clone_node = Node(node.val, []) visited[node] = clone_node # 队列用于 BFS queue = deque([node]) while queue: cur = queue.popleft() # 遍历当前节点的所有邻居 for neighbor in cur.neighbors: if neighbor not in visited: # 如果邻居没被克隆过，创建并加入队列 visited[neighbor] = Node(neighbor.val, []) queue.append(neighbor) # 将邻居的克隆节点加入当前节点克隆体的 neighbors 列表 visited[cur].neighbors.append(visited[neighbor]) return clone_node

复杂度分析

• 时间复杂度：
  “O(N)”，其中
  “N” 是图中节点的数量。每个节点和每条边最多被访问一次。
• 空间复杂度：
  “O(N)”，哈希表
  “visited” 需要存储所有节点的映射，递归栈或队列在最坏情况下（图退化为链表）也需要
  “O(N)” 的空间。

两种方法的对比

方法 优点 适用场景
DFS 代码简洁，逻辑直观 图深度不大，避免递归栈溢出
BFS 无递归栈溢出风险 图深度很大时更安全

如果你需要我帮你把这段代码改成 JavaScript 版本，或者想看 LeetCode 138（复制带随机指针的链表） 的类似解法，随时告诉我！