133 克隆图

题目描述#

给你无向连通图中一个节点的引用，返回该图的深拷贝。每个节点包含一个整数值 val 和邻居列表 Neighbors。

思路#

深拷贝图的难点在于图可能有环——如果不加记录地递归，会无限循环。用一个 visited 哈希表把"原节点 → 克隆节点"的映射存起来，就能同时解决两个问题：避免重复访问，以及在处理邻居时直接拿到已经创建好的克隆节点。

DFS 的流程：进入一个节点时，先检查它是否已经在 visited 里——有就直接返回对应的克隆节点；没有就先创建克隆节点并立即存入 visited（在递归邻居之前），然后遍历所有邻居递归克隆，把返回值追加到克隆节点的邻居列表里。

先存再递归这个顺序很关键：如果等邻居全处理完再存，遇到环时会在回到当前节点时找不到已有克隆，导致无限递归。

递归步骤图示#

以一个 4 节点的环形图为例：

原图：
1 —— 2
|    |
4 —— 3

每个节点的邻居：
1: [2, 4]
2: [1, 3]
3: [2, 4]
4: [3, 1]

从 dfs(1) 出发，下面追踪每一步的 visited 状态：

调用 dfs(1)
  visited 里没有 1
  创建 clone(1)，立即写入 visited
  visited = { 1 → clone(1) }
  遍历邻居 [2, 4]：

  ├─ 调用 dfs(2)
  │    visited 里没有 2
  │    创建 clone(2)，写入 visited
  │    visited = { 1 → clone(1), 2 → clone(2) }
  │    遍历邻居 [1, 3]：
  │
  │    ├─ 调用 dfs(1)
  │    │    visited 里有 1 ✓ 直接返回 clone(1)
  │    │
  │    └─ 调用 dfs(3)
  │         visited 里没有 3
  │         创建 clone(3)，写入 visited
  │         visited = { 1→clone(1), 2→clone(2), 3→clone(3) }
  │         遍历邻居 [2, 4]：
  │
  │         ├─ 调用 dfs(2)
  │         │    visited 里有 2 ✓ 直接返回 clone(2)
  │         │
  │         └─ 调用 dfs(4)
  │              visited 里没有 4
  │              创建 clone(4)，写入 visited
  │              visited = { 1→clone(1), 2→clone(2), 3→clone(3), 4→clone(4) }
  │              遍历邻居 [3, 1]：
  │              ├─ dfs(3)：visited 有 3 ✓ 返回 clone(3)
  │              └─ dfs(1)：visited 有 1 ✓ 返回 clone(1)
  │              clone(4).Neighbors = [clone(3), clone(1)]
  │              返回 clone(4)
  │
  │         clone(3).Neighbors = [clone(2), clone(4)]
  │         返回 clone(3)
  │
  │    clone(2).Neighbors = [clone(1), clone(3)]
  │    返回 clone(2)
  │
  └─ 调用 dfs(4)
       visited 里有 4 ✓ 直接返回 clone(4)

  clone(1).Neighbors = [clone(2), clone(4)]
  返回 clone(1)   ← 最终结果

可以看到，正是"先写入 visited 再递归"让 dfs(1) 在第二次被调用时能立刻命中缓存，打断了环路。

知识边界#

图的深拷贝必须用 visited 记录已克隆的节点，同时防环和复用已有克隆
先写入 visited 再递归邻居：这是处理有环图的标准顺序，顺序反了会栈溢出
本题 DFS 和 BFS 都可以做，思路对称；DFS 用递归更简洁，BFS 用队列更直观

代码#

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Neighbors []*Node
 * }
 */

func cloneGraph(node *Node) *Node {
    if node == nil {
        return nil
    }
    // 当前每个原节点到克隆节点的映射
    visited := make(map[*Node]*Node)
    var dfs func(*Node) *Node
    dfs = func(node *Node) *Node {
        // 当前节点已经克隆过，直接返回
        if cloneNode, ok := visited[node]; ok {
            return cloneNode
        }

        // 建立新克隆节点，然后遍历邻居
        cloneNode := &Node{
            Val: node.Val,
        }
        // 存入映射
        visited[node] = cloneNode

        // 开始处理邻居
        for _, neighbor := range node.Neighbors {
            cloneNode.Neighbors = append(cloneNode.Neighbors, dfs(neighbor))
        }
        return cloneNode
    }
    // 返回第一个克隆的节点
    return dfs(node)
}