Clone Graph（克隆图）

题目 / Problem

中文： 给定一个连通无向图中某个节点的引用，返回该图的深拷贝。

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

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

深拷贝要求：
A deep copy requires that:

为原图中的每个节点创建一个全新的节点对象。
A new node object is created for every original node.
克隆图具有与原图相同的节点值和连接关系。
The clone has the same node values and connections as the original.
克隆图中不能引用任何原图节点。
The cloned graph must not reference any original node.

English: Given a reference to a node in a connected undirected graph, return a deep copy of the graph.

Each node contains an integer value val and a list of neighboring nodes named neighbors.

为了简化测试，每个节点的值与它的一维下标相同。例如，第一个节点的 val 为 1，第二个节点的 val 为 2，依此类推。测试用例使用邻接表表示图。
For simplicity, each node's value equals its one-based index. The graph is represented in test cases using an adjacency list.

邻接表中的第 i 个数组列出节点 i + 1 的所有邻居。给定的节点引用始终是值为 1 的第一个节点。
The ith list contains all neighbors of node i + 1. The provided node reference is always the first node, whose value is 1.

需要注意：函数接收的是 Node 对象，而不是邻接表数组。邻接表只用于展示测试输入和输出。
Important: the function receives a Node object, not the adjacency-list array. The adjacency list is only the test representation.

示例 / Examples

Example 1

原图、正确深拷贝与错误克隆的对比 / Original graph, correct deep copy, and incorrect clones

Input:  adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]

1 ─── 2
│     │
│     │
4 ─── 3

图中共有四个节点：
The graph contains four nodes:

节点 1 的邻居是 2 和 4。
Node 1 has neighbors 2 and 4.
节点 2 的邻居是 1 和 3。
Node 2 has neighbors 1 and 3.
节点 3 的邻居是 2 和 4。
Node 3 has neighbors 2 and 4.
节点 4 的邻居是 1 和 3。
Node 4 has neighbors 1 and 3.

输入和输出的邻接表内容相同，但输出对应的是一组全新的节点对象。
The input and output adjacency lists contain the same values, but the output represents entirely new node objects.

Example 2

没有邻居的单节点图 / Single-node graph with no neighbors

Input:  adjList = [[]]
Output: [[]]

图中只有一个值为 1 的节点，并且它没有邻居。仍然需要创建并返回一个新的节点对象。
The graph contains one node with value 1 and no neighbors. A new node object must still be created and returned.

Example 3

Input:  adjList = []
Output: []

空邻接表表示空图，函数收到的 node 为 null，应返回 null。
An empty adjacency list represents an empty graph. The function receives null and should return null.

约束 / Constraints

图中的节点数在 [0, 100] 范围内。
The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 100
每个节点的 Node.val 都是唯一的。
Every node has a unique Node.val.
图中没有重复边和自环。
The graph contains no repeated edges and no self-loops.
图是连通的，可以从给定节点访问所有节点。
The graph is connected, and every node is reachable from the given node.

解题关键：节点映射 / Key Idea: Node Mapping

图可能存在环。例如 Example 1 中可以沿着：
A graph may contain cycles. In Example 1, one can follow:

1 → 2 → 3 → 4 → 1 → ...

如果每次访问节点都直接递归创建副本，会无限递归，并且同一个原节点可能被克隆多次。
If every visit recursively creates a new copy, traversal never ends and the same original node may be cloned multiple times.

因此使用 Map 保存一一对应关系：
Use a Map to store a one-to-one correspondence:

原节点对象 / Original Node → 克隆节点对象 / Cloned Node

这个映射同时承担两个作用：
This mapping serves two purposes:

标记原节点已经访问过，防止环导致重复遍历。
Marks the original node as visited, preventing repeated traversal through cycles.
保证每个原节点只对应一个克隆节点，正确保留共享邻居和连接关系。
Ensures every original node has exactly one clone, preserving shared neighbors and graph structure.

Map 的键必须使用原节点对象，而不是节点值。虽然本题保证节点值唯一，但以对象为键更准确地表达克隆关系，也适用于节点值可能重复的通用图。
Use original node objects as map keys rather than values. Although values are unique here, object keys represent the cloning relationship precisely and also work for graphs with duplicate values.

解题思路一：DFS / Approach 1: Depth-First Search

对于当前原节点 current：
For the current original node current:

如果映射中已经存在它，直接返回之前创建的克隆节点。
If it already exists in the map, return the previously created clone.
创建一个新的克隆节点，并立即放入映射。
Create a new clone and immediately store it in the map.
递归克隆每个邻居，并将克隆后的邻居加入当前克隆节点的 neighbors。
Recursively clone every neighbor and append each cloned neighbor to the clone's neighbors list.
返回克隆节点。
Return the cloned node.

必须在递归邻居之前将克隆节点放入映射，否则遇到环时，节点还没有被标记，会造成无限递归。
Store the clone before recursing into neighbors. Otherwise, a cycle may revisit the node before it is marked and cause infinite recursion.

JavaScript 实现 / JavaScript Implementation

/**
 * Definition for a Node.
 * function Node(val, neighbors) {
 *   this.val = val === undefined ? 0 : val;
 *   this.neighbors = neighbors === undefined ? [] : neighbors;
 * }
 */

/**
 * @param {Node} node
 * @return {Node}
 */
function cloneGraph(node) {
  if (node === null) {
    return null;
  }

  const clones = new Map();

  function clone(current) {
    if (clones.has(current)) {
      return clones.get(current);
    }

    const copy = new Node(current.val);
    clones.set(current, copy);

    for (const neighbor of current.neighbors) {
      copy.neighbors.push(clone(neighbor));
    }

    return copy;
  }

  return clone(node);
}

DFS 执行过程 / DFS Walkthrough

以 Example 1 从节点 1 开始：
Starting from node 1 in Example 1:

步骤 / Step	当前节点 / Current	操作 / Action	映射中的节点 / Mapped Nodes
1	1	创建 `1'` / Create clone `1'`	`{1 → 1'}`
2	2	创建 `2'` / Create clone `2'`	`{1 → 1', 2 → 2'}`
3	1	已存在，返回 `1'` / Already mapped; return `1'`	不变 / Unchanged
4	3	创建 `3'` / Create clone `3'`	加入 `3 → 3'`
5	2	已存在，返回 `2'` / Already mapped; return `2'`	不变 / Unchanged
6	4	创建 `4'` / Create clone `4'`	加入 `4 → 4'`

后续再次遇到节点 1 或 3 时，直接复用映射中的克隆节点。最终每个原节点只创建一个副本。
When nodes 1 or 3 are encountered again, their existing clones are reused. Exactly one copy is created for each original node.

解题思路二：BFS / Approach 2: Breadth-First Search

BFS 同样使用节点映射，但通过队列逐个处理原节点：
BFS uses the same node mapping but processes original nodes through a queue:

先创建起始节点的副本并加入映射。
Create the starting node's clone and add it to the map.
将原始起始节点加入队列。
Enqueue the original starting node.
对当前节点的每个邻居，如果尚未克隆，就创建副本并将原邻居加入队列。
For each neighbor, create and enqueue it if it has not been cloned.
无论邻居是否是新发现的，都将对应克隆节点加入当前副本的邻居列表。
Whether newly discovered or not, append the corresponding cloned neighbor to the current clone's neighbor list.

function cloneGraphBFS(node) {
  if (node === null) {
    return null;
  }

  const clones = new Map([[node, new Node(node.val)]]);
  const queue = [node];
  let front = 0;

  while (front < queue.length) {
    const current = queue[front++];
    const currentCopy = clones.get(current);

    for (const neighbor of current.neighbors) {
      if (!clones.has(neighbor)) {
        clones.set(neighbor, new Node(neighbor.val));
        queue.push(neighbor);
      }

      currentCopy.neighbors.push(clones.get(neighbor));
    }
  }

  return clones.get(node);
}

这里使用 front 索引读取队列，避免调用 JavaScript 数组的 shift()。
An index named front reads from the queue instead of using JavaScript's shift().

复杂度 / Complexity

设图中有 V 个节点和 E 条无向边。
Let the graph contain V vertices and E undirected edges.

时间复杂度：O(V + E)。每个节点访问一次；邻接表中的每条无向边会从两端各读取一次。
Time: O(V + E). Every vertex is visited once, and each undirected edge appears in two adjacency lists.
空间复杂度：O(V)，映射保存所有节点；DFS 使用递归栈，BFS 使用队列。
Space: O(V) for the map, plus a DFS recursion stack or BFS queue containing at most O(V) nodes.
克隆图本身需要 O(V + E) 空间，这是必须返回的结果。
The cloned graph itself requires O(V + E) space as the required output.

DFS 与 BFS 对比 / DFS vs. BFS

方法 / Method	时间 / Time	辅助空间 / Auxiliary Space	特点 / Notes
DFS	`O(V + E)`	`O(V)`	代码简洁，递归构建邻居 / Concise recursive construction
BFS	`O(V + E)`	`O(V)`	不依赖递归栈 / Avoids recursion stack

两种方法都必须使用原节点到克隆节点的映射。选择哪一种主要取决于遍历风格和递归深度限制。
Both methods require the original-to-clone map. The choice mainly depends on traversal style and recursion-depth concerns.

浅拷贝为什么不够？ / Why Is a Shallow Copy Insufficient?

以下写法只复制了起始节点，邻居数组仍包含原图节点：
The following creates only a new starting node while retaining original graph nodes in its neighbor list:

// 错误示例 / Incorrect example
const copy = new Node(node.val, [...node.neighbors]);

修改克隆图中的某个邻居时会影响原图，因为邻居对象仍然共享。深拷贝必须递归或迭代创建所有节点，并重新连接克隆节点。
Changing a neighbor through the clone would affect the original graph because the neighbor objects are shared. A deep copy must create every node and reconnect only cloned nodes.

易错点 / Common Pitfalls

函数参数是节点引用，不是邻接表数组。
The function parameter is a node reference, not an adjacency-list array.
空图对应 node === null，应返回 null。
An empty graph corresponds to node === null, so return null.
必须进行深拷贝，克隆图的邻居不能引用原节点。
Perform a deep copy; cloned neighbors must not reference original nodes.
创建克隆节点后应立即放入映射，再遍历邻居。
Store a clone in the map immediately after creating it and before traversing neighbors.
图中可能存在环，不能仅依赖递归终止条件，必须记录已克隆节点。
Graphs may contain cycles, so a clone map is required beyond ordinary recursion base cases.
同一个原节点只能创建一个克隆节点，否则会破坏图的共享连接结构。
Create exactly one clone per original node or shared graph connections will be corrupted.
输出邻接表看起来与输入相同，并不意味着可以直接返回原节点。对象身份必须完全独立。
Identical-looking adjacency lists do not permit returning the original node; object identities must be independent.

Clone Graph