这是一道经典的图遍历问题。为了实现对图的“深拷贝”，我们需要遍历原图，并创建所有节点的新实例。由于图可能包含环（例如 1 连接 2，2 又连接 1），我们必须记录已经访问并克隆过的节点，以避免无限循环。 这里提供两种常见的 JavaScript 实现方式：深度优先搜索 (DFS) 和 广度优先搜索 (BFS)。

方法一：深度优先搜索 (DFS) - 递归

这是最直观的方法。我们使用一个哈希表（Map）来存储 原节点 -> 新节点 的映射。 思路：

1. 如果节点为空，返回 null。
2. 如果当前节点已经被克隆过（存在于 Map 中），直接返回 Map 中的克隆节点。
3. 如果没有被克隆过，创建一个新的节点，将其存入 Map。
4. 递归克隆当前节点的所有邻居，并将克隆后的邻居添加到新节点的邻居列表中。

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */
/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
    // 边界情况处理：如果输入为空
    if (!node) return null;
    // 使用 Map 存储原节点到克隆节点的映射，防止重复克隆和死循环
    const visited = new Map();
    // 定义 DFS 递归函数
    function dfs(originalNode) {
        // 1. 如果该节点已经被克隆过，直接返回克隆后的节点
        if (visited.has(originalNode)) {
            return visited.get(originalNode);
        }
        // 2. 创建克隆节点
        // 注意：这里暂时不处理 neighbors，因为它们可能还没被创建
        const cloneNode = new Node(originalNode.val, []);
        
        // 3. 将映射存入 Map，必须在递归调用之前存储，防止环导致的死循环
        visited.set(originalNode, cloneNode);
        // 4. 遍历邻居，递归克隆
        for (const neighbor of originalNode.neighbors) {
            // 将克隆后的邻居加入当前克隆节点的 neighbors 列表
            cloneNode.neighbors.push(dfs(neighbor));
        }
        return cloneNode;
    }
    // 从入口节点开始 DFS
    return dfs(node);
};

---

方法二：广度优先搜索 (BFS) - 迭代

如果你不想使用递归，或者担心递归深度过深，可以使用 BFS。 思路：

1. 使用队列来进行层序遍历。
2. 同样使用 Map 来记录已克隆的节点。
3. 初始时克隆第一个节点放入队列。
4. 只要队列不为空，取出节点，遍历其邻居：
   • 如果邻居没被克隆过，克隆它并放入队列。
   • 将克隆后的邻居添加到当前节点的克隆节点的邻居列表中。

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */
/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
    if (!node) return null;
    // Map 用于存储 原节点 -> 克隆节点 的映射
    const visited = new Map();
    // 队列用于 BFS 遍历
    const queue = [];
    // 1. 克隆第一个节点并放入队列和 Map
    const cloneNode = new Node(node.val, []);
    visited.set(node, cloneNode);
    queue.push(node);
    // 2. 开始 BFS 遍历
    while (queue.length > 0) {
        const currentOriginal = queue.shift();
        
        // 遍历当前原节点的邻居
        for (const neighbor of currentOriginal.neighbors) {
            // 如果邻居没有被克隆过
            if (!visited.has(neighbor)) {
                // 克隆邻居
                const newNeighbor = new Node(neighbor.val, []);
                visited.set(neighbor, newNeighbor);
                // 将原邻居加入队列，以便后续处理它的邻居
                queue.push(neighbor);
            }
            
            // 这一步是关键：
            // 获取原节点对应的克隆节点
            // 将克隆后的邻居添加到当前克隆节点的邻居列表中
            visited.get(currentOriginal).neighbors.push(visited.get(neighbor));
        }
    }
    return cloneNode;
};

复杂度分析

两种方法的时间复杂度和空间复杂度相同：

• 时间复杂度：$O(N)$，其中 $N$ 是节点的数量。我们需要遍历图中的每一个节点和每一条边。
• 空间复杂度：$O(N)$。哈希表 visited 存储了所有节点的映射。在 DFS 中是递归栈的开销，在 BFS 中是队列的开销，最坏情况下都是 $O(N)$。