乐扣等题(133)js--克隆图

解题步骤：
①深度或广度优先遍历所有节点；

②拷贝所有节点，存储起来；

③将拷贝的节点，按照原图的连接方法进行连接。

首先是判断node，不符合条件直接返回即可，不用浪费时间。

然后再书写完整的深度优先遍历的过程，随后需要拷贝节点并存储。拷贝的时候比较简单，只要用

const nCopy=new Node(n.val)

 就可以了，现在不传入neighbors会自动变成一个空数组。存储可以巧妙地和原节点的遍历形成一个映射，将visited新建的Set改成Map，然后让n对应nCopy即可，至此完成了节点的拷贝和存储。

接下来是拷贝边。

nCopy的neighbors和原节点对应上即可。

最后返回拷贝到的克隆图，也是获取node节点的克隆即可。

1.  
   /**
2.  
   * // Definition for a Node.
3.  
   * function Node(val, neighbors) {
4.  
   * this.val = val === undefined ? 0 : val;
5.  
   * this.neighbors = neighbors === undefined ? [] : neighbors;
6.  
   * };
7.  
   */
8.  
    
9.  
   /**
10.  
    * @param {Node} node
11.  
    * @return {Node}
12.  
    */
13.  
    var cloneGraph = function(node) {
14.  
    if(!node) {return;}
15.  
    const visited=new Map();
16.  
    const dfs=(n)=> {
17.  
    const nCopy=new Node(n.val)
18.  
    visited.set(n, nCopy);
19.  
    (n.neighbors || []).forEach( c=> {
20.  
    if(!visited.has(c)){
21.  
    dfs(c)
22.  
    }
23.  
    nCopy.neighbors.push(visited.get(c))
24.  
    })
25.  
    }
26.  
    dfs(node)
27.  
    return visited.get(node)
28.  
    };

也可以用广度优先遍历实现

1.  
   /**
2.  
   * // Definition for a Node.
3.  
   * function Node(val, neighbors) {
4.  
   * this.val = val === undefined ? 0 : val;
5.  
   * this.neighbors = neighbors === undefined ? [] : neighbors;
6.  
   * };
7.  
   */
8.  
    
9.  
   /**
10.  
    * @param {Node} node
11.  
    * @return {Node}
12.  
    */
13.  
    var cloneGraph = function(node) {
14.  
    if(!node) {return;}
15.  
    const visited=new Map();
16.  
    visited.set(node, new Node(node.val));
17.  
    const q=[node];
18.  
    while(q.length) {
19.  
    const n=q.shift();
20.  
    (n.neighbors || []).forEach(c=> {
21.  
    if(!visited.has(c)) {
22.  
    q.push(c);
23.  
    visited.set(c, new Node(c.val));
24.  
    }
25.  
    visited.get(n).neighbors.push(visited.get(c))
26.  
    })
27.  
    }
28.  
    return visited.get(node)
29.  
    };

这篇好文章是转载于：学新通技术网