LeetCode：133. 克隆图

深度优先

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function (node) {
    if (!node) return;
    const visited = new Map() // 访问过的节点

    // 深度优先
    const dfs = (n) => {       
        const nCp = new Node(n.val)
        visited.set(n, nCp); // 设置访问过的，同时建立映射关系（克隆）
        (n.neighbors || []).forEach(ne => {           
            if (!visited.has(ne)) {
                dfs(ne)
            }
            // 相邻节点同样赋值一份，但需要从 visited 里面拿
            nCp.neighbors.push(visited.get(ne)) 
        })
    }
    dfs(node)

    // 返回克隆的节点
    return visited.get(node) 
};

广度优先

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function (node) {
    if (!node) return;
    const visited = new Map() // 访问过的

    // 设置第一个访问过的，同时建立映射关系（克隆）
    visited.set(node, new Node(node.val)) 

    // 广度优先
    const q = [node]
    while (q.length) {
        const n = q.shift();
        (n.neighbors || []).forEach(ne => {
            if (!visited.has(ne)) {
                q.push(ne)

                // 设置访问过的，同时建立映射关系（克隆）
                visited.set(ne, new Node(ne.val))
            }

            // 相邻节点同样赋值一份，但需要从 visited 里面拿
            visited.get(n).neighbors.push(visited.get(ne))
        })
    }

    // 返回克隆的节点
    return visited.get(node)
};