LeetCode 133（克隆图）

通过深度优先遍历的方式进行实现

• 时间复杂度：O (n)

• 空间复杂度：O (n)

  function cloneGraph(node) {
    if (!node) return;
    const visited = new Map();
    const dfs = (n) => {
        const newNode = new Node(n.val);
        visited.set(n, newNode);
        (n.neighbors || []).forEach((next) => {
            if (!visited.has(next)) {
                dfs(next);
            }
            newNode.neighbors.push(visited.get(next));
        });
    };
    dfs(node);
    return visited.get(node);
  }

代码中主要访问了图的所有节点，所以时间复杂度是O (n) n 代表节点数，空间复杂度是O (n) ，因为我们定义了 Map 数据结构，里面用来存放所有节点。

这里可能会有同学问，递归的空间复杂度不是递归的深度吗？不是也要算进去吗？因为递归的深度很大可能性是小于 Map 的长度的，所以我们以空间复杂度最大值为准。

通过广度优先遍历的方式进行实现

• 时间复杂度：O (n)

• 空间复杂度：O (n)

  function cloneGraph(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((next) => {
            if (!visited.has(next)) {
                q.push(next);
                visited.set(next, new Node(next.val));
            }
            visited.get(n).neighbors.push(visited.get(next));
        });
    }
    return visited.get(node);
  }

首先时间复杂度依然是 O (n) ，n 代表所有节点数，因为广度优先遍历会访问图的所有节点。空间复杂度为 O (n) 因为我们使用了队列，队列的长度最坏情况下可能是所有的节点数。