今日打卡： leetcode 133. 克隆图 克隆图 https://leetcode.cn/problems/clone-graph/

题目描述

给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。

图中的每个节点都包含它的值 val（int）和其邻居的列表（list[Node]）。

节点定义

function Node(val, neighbors) {
    this.val = val === undefined ? 0 : val;
    this.neighbors = neighbors === undefined ? [] : neighbors;
}

解法一：DFS（深度优先搜索）+ 哈希表

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

    // 哈希表用于存储已访问过的节点，key是原节点，value是克隆节点
    const visited = new Map();

    const dfs = (node) => {
        // 如果已经访问过这个节点，直接返回克隆节点
        if (visited.has(node)) {
            return visited.get(node);
        }

        // 克隆当前节点
        const cloneNode = new Node(node.val);
        // 将克隆节点存入哈希表
        visited.set(node, cloneNode);

        // 递归克隆所有邻居节点
        for (let neighbor of node.neighbors) {
            cloneNode.neighbors.push(dfs(neighbor));
        }

        return cloneNode;
    };

    return dfs(node);
};

时间复杂度：O(N)，其中 N 是图中节点的数量，每个节点只访问一次 空间复杂度：O(N)，哈希表和递归栈空间

解法二：BFS（广度优先搜索）+ 哈希表

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

    // 哈希表存储已访问的节点
    const visited = new Map();

    // 克隆起始节点
    const cloneNode = new Node(node.val);
    visited.set(node, cloneNode);

    // 使用队列进行BFS
    const queue = [node];

    while (queue.length > 0) {
        const curr = queue.shift();

        // 遍历当前节点的所有邻居
        for (let neighbor of curr.neighbors) {
            // 如果邻居节点还没被访问过
            if (!visited.has(neighbor)) {
                // 克隆邻居节点
                visited.set(neighbor, new Node(neighbor.val));
                // 将邻居节点加入队列
                queue.push(neighbor);
            }
            // 将克隆的邻居节点添加到当前克隆节点的邻居列表中
            visited.get(curr).neighbors.push(visited.get(neighbor));
        }
    }

    return cloneNode;
};

时间复杂度：O(N)，每个节点只访问一次 空间复杂度：O(N)，哈希表和队列空间

核心思路

1. 使用哈希表记录访问过的节点：防止重复访问，避免无限循环（图中可能有环）
2. 深拷贝节点：创建新的节点对象，而不是引用原节点
3. 递归/迭代克隆邻居：确保所有连接关系都被正确复制

测试用例

// 测试用例：[[2,4],[1,3],[2,4],[1,3]]
const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
const node4 = new Node(4);

node1.neighbors = [node2, node4];
node2.neighbors = [node1, node3];
node3.neighbors = [node2, node4];
node4.neighbors = [node1, node3];

const cloned = cloneGraph(node1);
console.log(cloned.val); // 1
console.log(cloned.neighbors.map(n => n.val)); // [2, 4]