LeetCode 133：克隆图 | BFS/DFS

LeetCode 133：克隆图 | BFS/DFS

引言

克隆图（Clone Graph）是 LeetCode 第 133 题，难度为 Medium。题目要求深拷贝一个无向图。

算法实现

def cloneGraph(node): if not node: return None visited = {node: Node(node.val)} queue = [node] while queue: n = queue.pop(0) for neighbor in n.neighbors: if neighbor not in visited: visited[neighbor] = Node(neighbor.val) queue.append(neighbor) visited[n].neighbors.append(visited[neighbor]) return visited[node]

复杂度分析

时间复杂度：O(V + E)
空间复杂度：O(V)

总结

使用哈希表记录原节点到新节点的映射，避免重复克隆。