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);
};