克隆图

Tips

题目类型: Graph

题目

给你无向**连通图中一个节点的引用, 请你返回该图的深拷贝**(克隆).

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

class Node {
    public int val;
    public List<Node> neighbors;
}

**测试用例格式: **

简单起见, 每个节点的值都和它的索引相同. 例如, 第一个节点值为 1(val = 1), 第二个节点值为 2(val = 2), 以此类推. 该图在测试用例中使用邻接列表表示.

邻接列表是用于表示有限图的无序列表的集合. 每个列表都描述了图中节点的邻居集.

给定节点将始终是图中的第一个节点(值为 1). 你必须将给定节点的拷贝作为对克隆图的引用返回.

提示:

这张图中的节点数在 [0, 100] 之间.
1 <= Node.val <= 100
每个节点值 Node.val 都是唯一的,
图中没有重复的边, 也没有自环.
图是连通图, 你可以从给定节点访问到所有节点.

示例

**示例 1: **

133-clone-graph

输入: adjList = [[2,4],[1,3],[2,4],[1,3]]
输出: [[2,4],[1,3],[2,4],[1,3]]
解释:
图中有 4 个节点.
节点 1 的值是 1, 它有两个邻居: 节点 2 和 4.
节点 2 的值是 2, 它有两个邻居: 节点 1 和 3.
节点 3 的值是 3, 它有两个邻居: 节点 2 和 4.
节点 4 的值是 4, 它有两个邻居: 节点 1 和 3.

**示例 2: **

133-clone-graph

输入: adjList = [[]]
输出: [[]]
解释: 输入包含一个空列表. 该图仅仅只有一个值为 1 的节点, 它没有任何邻居.

**示例 3: **

输入: adjList = []
输出: []
解释: 这个图是空的, 它不含任何节点.

题解

特判: 如果输入节点为空, 则直接返回空.
创建哈希表: 创建一个哈希表 visited, 用于存储原节点和拷贝节点的对应关系.
深度优先搜索:
- 如果当前节点为空, 则返回空.
- 如果当前节点已经在 visited 中, 则直接返回对应的拷贝节点.
- 创建一个新的拷贝节点, 其值与当前节点相同.
- 将当前节点和拷贝节点存入 visited.
- 递归遍历当前节点的每个邻居节点, 并将拷贝邻居节点添加到拷贝节点的邻居列表中.
- 返回拷贝节点.
调用 DFS: 从输入节点开始调用 DFS 函数, 即可得到深拷贝图.

/**
 * // 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
  }

  const visited = new Map()

  function dfs(curr) {
    if (!curr) {
      return null
    }

    if (visited.has(curr)) {
      return visited.get(curr)
    }

    const copyNode = { val: curr.val, neighbors: [] }
    visited.set(curr, copyNode)

    for (const neighbor of curr.neighbors) {
      copyNode.neighbors.push(dfs(neighbor))
    }

    return copyNode
  }

  return dfs(node)
}

时间复杂度: O(V + E), 其中 V 是节点数, E 是边数.
空间复杂度: O(V), 用于存储 visited 哈希表和递归调用栈.

题目​

题解​

题目

题解