❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！
- 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
- 导航：
- LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
- 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
- python源码解读：解读python的源代码与调用关系，快速提升代码质量
- python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
- 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识
期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️
解读力扣第 133 题：克隆图
在本篇文章中，我们将详细解读力扣第 133 题“克隆图”。通过学习本篇文章，读者将掌握如何使用广度优先搜索（BFS）和深度优先搜索（DFS）来克隆一个图。
问题描述
力扣第 133 题“克隆图”描述如下：
给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。图中的每个节点都包含它的值
val（int）和它的邻居列表（List[Node]）。
示例 1:
输入：adjList = [[2,4],[1,3],[2,4],[1,3]] 输出：[[2,4],[1,3],[2,4],[1,3]] 解释： 节点 1 的值是 1，它有两个邻居：节点 2 和 4 。 节点 2 的值是 2，它有两个邻居：节点 1 和 3 。 节点 3 的值是 3，它有两个邻居：节点 2 和 4 。 节点 4 的值是 4，它有两个邻居：节点 1 和 3 。
示例 2:
输入：adjList = [[]] 输出：[[]] 解释：输入包含一个空列表。该图仅有一个节点，没有邻居。
示例 3:
输入：adjList = [] 输出：[] 解释：这个图是空的，它没有任何节点。
解题思路
- 初步分析：
- 我们需要克隆一个图，即对每个节点创建一个新的节点，并复制其邻居关系。
- 可以使用广度优先搜索（BFS）或深度优先搜索（DFS）来遍历图并进行克隆。
- 广度优先搜索（BFS）方法：
- 使用队列进行图的遍历，从起始节点开始，逐层克隆每个节点及其邻居。
- 需要一个哈希表来存储已经克隆的节点，防止重复克隆。
- 深度优先搜索（DFS）方法：
- 使用递归进行图的遍历，从起始节点开始，递归克隆每个节点及其邻居。
- 同样需要一个哈希表来存储已经克隆的节点，防止重复克隆。
代码实现
广度优先搜索（BFS）方法
class Node: def __init__(self, val = 0, neighbors = None): self.val = val self.neighbors = neighbors if neighbors is not None else [] def cloneGraph(node): if not node: return None clone_map = {} queue = deque([node]) clone_map[node] = Node(node.val) while queue: current = queue.popleft() for neighbor in current.neighbors: if neighbor not in clone_map: clone_map[neighbor] = Node(neighbor.val) queue.append(neighbor) clone_map[current].neighbors.append(clone_map[neighbor]) return clone_map[node] # 测试案例 def build_graph(adjList): if not adjList: return None nodes = [Node(i + 1) for i in range(len(adjList))] for i, neighbors in enumerate(adjList): nodes[i].neighbors = [nodes[j - 1] for j in neighbors] return nodes[0] adjList1 = [[2, 4], [1, 3], [2, 4], [1, 3]] graph1 = build_graph(adjList1) cloned_graph1 = cloneGraph(graph1) # 验证克隆图的结构 adjList2 = [[]] graph2 = build_graph(adjList2) cloned_graph2 = cloneGraph(graph2) # 验证克隆图的结构 adjList3 = [] graph3 = build_graph(adjList3) cloned_graph3 = cloneGraph(graph3) # 验证克隆图的结构
深度优先搜索（DFS）方法
class Node: def __init__(self, val = 0, neighbors = None): self.val = val self.neighbors = neighbors if neighbors is not None else [] def cloneGraph(node): if not node: return None clone_map = {} def dfs(node): if node in clone_map: return clone_map[node] clone_node = Node(node.val) clone_map[node] = clone_node for neighbor in node.neighbors: clone_node.neighbors.append(dfs(neighbor)) return clone_node return dfs(node) # 测试案例 def build_graph(adjList): if not adjList: return None nodes = [Node(i + 1) for i in range(len(adjList))] for i, neighbors in enumerate(adjList): nodes[i].neighbors = [nodes[j - 1] for j in neighbors] return nodes[0] adjList1 = [[2, 4], [1, 3], [2, 4], [1, 3]] graph1 = build_graph(adjList1) cloned_graph1 = cloneGraph(graph1) # 验证克隆图的结构 adjList2 = [[]] graph2 = build_graph(adjList2) cloned_graph2 = cloneGraph(graph2) # 验证克隆图的结构 adjList3 = [] graph3 = build_graph(adjList3) cloned_graph3 = cloneGraph(graph3) # 验证克隆图的结构
复杂度分析
- 时间复杂度：O(N)，其中 N 是图中节点的数量。每个节点和每条边都会被访问一次。
- 空间复杂度：O(N)，用于存储哈希表和队列/递归栈的空间。
总结
本文详细解读了力扣第 133 题“克隆图”，通过广度优先搜索（BFS）和深度优先搜索（DFS）两种不同的解法，帮助读者深入理解图的克隆问题的解决思路。希望读者通过本文的学习，能够在力扣刷题的过程中更加得心应手。
参考资料
- 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- 力扣官方题解
🌹🌹如果觉得这篇文对你有帮助的话，记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励，非常感谢 ❥(^_-)
❤️❤️作者知识有限，如有错误，请各位大佬评论区批评指正，不胜感激❥(^_-)
欢迎关注微信公众号 数据分析螺丝钉
