克隆图-LeetCode

133. 克隆图 (Clone Graph)

🎯 问题描述（来源于LeetCode）

描述：给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（int）和其邻居的列表（list[Node]）。

class Node {
    public int val;
    public List neighbors;
}

测试用例格式：
简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

• 示例 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。

  (注：这是一个环形结构 1-2-3-4-1)

💻 解题思路

思路1：深度优先搜索 (DFS) + 哈希表

思路描述

这道题的核心难点在于图中可能存在环（或者回路）。如果直接使用递归遍历，程序会在两个节点之间无限循环（例如 A 指向 B，B 指向 A）。

解决方案：使用一个哈希表（字典）充当“备忘录”。

1. 映射关系：哈希表 visited 存储 <原节点, 克隆节点> 的映射。
2. 终止条件：在递归开始前，先检查当前节点是否已经在 visited 中。
   • 如果在，说明该节点已经被克隆过了，直接返回对应的克隆节点（避免死循环）。
   • 如果不在，则创建新节点，存入哈希表，然后递归处理其邻居。

思路1：代码实现

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return None
        
        # 哈希表：记录 原节点 -> 新节点 的映射
        visited = {}

        def dfs(original_node):
            # 1. 如果已经克隆过，直接返回克隆节点（核心：防止死循环）
            if original_node in visited:
                return visited[original_node]
            
            # 2. 创建新节点（只复制值，邻居列表暂时为空）
            clone_node = Node(original_node.val, [])
            
            # 3. 立即将新节点存入哈希表，建立映射关系
            visited[original_node] = clone_node
            
            # 4. 递归克隆所有邻居节点
            # 遍历原节点的邻居，将返回的克隆节点加入当前克隆节点的邻居列表
            for neighbor in original_node.neighbors:
                clone_node.neighbors.append(dfs(neighbor))
            
            return clone_node

        return dfs(node)

思路1：执行流程监测（针对示例 [[2,4],[1,3],[2,4],[1,3]]）

假设输入图为环形结构：1-2-3-4-1。

步骤	当前操作	递归层级	visited 状态变化	说明
1	dfs(Node 1)	1	{1: Clone(1)}	创建 Clone(1)，存入字典，开始遍历邻居 [2, 4]
2	dfs(Node 2)	2	{1: Clone(1), 2: Clone(2)}	创建 Clone(2)，存入字典，开始遍历邻居 [1, 3]
3	dfs(Node 1)	3	{1: Clone(1), 2: Clone(2)}	发现 Node 1 已在 visited，直接返回 Clone(1)
4	dfs(Node 3)	3	{1: Clone(1), 2: Clone(2), 3: Clone(3)}	继续 Node 2 的邻居，创建 Clone(3)，遍历 [2, 4]
5	dfs(Node 2)	4	{... 3: Clone(3)}	发现 Node 2 已在 visited，直接返回 Clone(2)
6	dfs(Node 4)	4	{... 3: Clone(3), 4: Clone(4)}	继续 Node 3 的邻居，创建 Clone(4)，遍历 [1, 3]
7	dfs(Node 1)	5	{... 4: Clone(4)}	发现 Node 1 已在 visited，返回 Clone(1)
8	dfs(Node 3)	5	{... 4: Clone(4)}	发现 Node 3 已在 visited，返回 Clone(3)

结果：所有节点被正确克隆且连接关系保持一致。

思路1：📊 性能分析

提交结果

• 运行时间：56ms击败51.47%
• 内存消耗：19.45MB击败86.90%

复杂度验证

• 时间复杂度：$O(N + M)$
  • 其中 $N$ 是节点数，$M$ 是边数。我们需要遍历图中的每一个节点和每一条边各一次。
• 空间复杂度：$O(N)$
  • 哈希表 visited 需要存储所有 $N$ 个节点。
  • 递归调用栈的深度在最坏情况下（图退化为链表）也是 $O(N)$。

思考

1. 为什么不能直接修改原节点？ 题目要求“深拷贝”，意味着必须创建全新的节点对象。修改原节点属性（如加一个 visited 标记）虽然能解决遍历问题，但不符合题目对内存隔离的要求。
2. BFS 做法：这道题也可以用广度优先搜索（BFS）配合队列实现。逻辑类似：使用队列存储待处理的节点，每次从队列取出一个节点，克隆它并处理其邻居，如果邻居未被克隆则入队。