[数据结构与算法]克隆图

电玩女神 2022-12-12 02:25 193阅读 0赞

深度优先遍历：

/** * // 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
          const visited = new Map()
          const dfs = (n) => { 
            const nCopy = new Node(n.val)
            visited.set(n, nCopy)
            ;(n.neighbors || []).forEach(ne => {  // 注意这里要加分号,防止理解为set()()
              if (!visited.has(ne)) { 
                dfs(ne)
              }
              nCopy.neighbors.push(visited.get(ne)) // 因为先dfs(ne)了,所以这里肯定能get到ne
            })
          }
          dfs(node)
          return visited.get(node)
        };

广度优先遍历：

/** * // 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
          const visited = new Map()
          const nCopy = new Node(node.val)
          visited.set(node, nCopy)
          const q = [node]
          while (q.length) { 
            const n = q.shift()
            ;(n.neighbors || []).forEach(ne => { 
              if (!visited.has(ne)) { 
                q.push(ne)
                const nCopy = new Node(ne.val)
                visited.set(ne, nCopy)
              }
              visited.get(n).neighbors.push(visited.get(ne))
            })
          }
          return visited.get(node)
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，193人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构与算法之图结构】案例

【数据结构与算法之图结构】案例文章目录【数据结构与算法之图结构】案例 1 迷宫问题 1 迷宫问题如

超、凢脫俗/ 2024年03月25日 16:38/ 0 赞/ 125 阅读

相关算法与数据结构之图

重要概念 1. 在数据结构中，线性结构，树形结构和图形结构数据元素之间分别存着一对一，一对多，多对多的联系。 2. n个顶点的连通图至少有n-1条边。 3. 有向图G

水深无声/ 2022年12月17日 04:25/ 0 赞/ 199 阅读

相关 [数据结构与算法]克隆图

深度优先遍历： / // Definition for a Node. function Node(val, neighbors) { this.val = v

电玩女神/ 2022年12月12日 02:25/ 0 赞/ 194 阅读

相关【数据结构与算法】图

一：如何理解“图” 1，图和树一样都是非线性表数据结构，和树不同的是图是一种更加复杂的非线性表结构 2，树中的元素称之为节点，图中的元素则称之为顶点。 3，顶点可以

港控/mmm°/ 2022年11月30日 04:20/ 0 赞/ 194 阅读

相关算法-图-克隆图

算法-图-克隆图 1 题目概述 1.1 题目出处 https://leetcode-cn.com/problems/clone-graph/ 1.2 题目

小鱼儿/ 2022年11月26日 12:57/ 0 赞/ 169 阅读

相关数据结构与算法之图

图跟树一样，也是非线性结构，咋看起来有点复杂，其实它很简单。树具有层次关系，上层元素可以与下一个多个元素连接，但是只能和上层的一个元素连接。在图结构中，节点间的连接是任意的，任

梦里梦外;/ 2022年06月07日 02:23/ 0 赞/ 200 阅读

相关数据结构与算法——图论基础与图存储结构

![640?wx\_fmt=png][640_wx_fmt_png] 1 前言由于后续更新「面试专场」的好几篇文章都涉及到图这种数据结构，因此打算先普及一下图

左手的ㄟ右手/ 2022年02月28日 11:40/ 0 赞/ 278 阅读

相关数据结构与算法---5（图）

图在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素都只有一个直接前驱和直接后继；在树形结构中，数据元素之间有着明显的层次结构，但是每一个元素肯定值只有一

「爱情、让人受尽委屈。」/ 2022年02月26日 06:28/ 0 赞/ 382 阅读

相关 C++数据结构与算法（图）

> 回顾：线性表中，每个元素只有一个直接前驱和直接后继，在树形结构中，数据之间是层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。但这都

谁借莪１个温暖的怀抱￠/ 2021年10月31日 16:30/ 0 赞/ 411 阅读

相关数据结构与算法之图

图基本概念无向图和有向图 ![70][] 前一个不带箭头的就是无向图，后一个带尖头的就是有向图子图如果图G中包含G1，那么G1就是G的

桃扇骨/ 2021年06月11日 15:11/ 0 赞/ 560 阅读