大家好，我是速冻鱼🐟，一条水系前端💦，喜欢花里胡哨💐，持续沙雕🌲，是隔壁寒草🌿的好兄弟，刚开始写文章。 如果喜欢我的文章，可以关注➕点赞，为我注入能量，与我一同成长吧～
前言🌧️
算法，对前端人来说陌生又熟悉，很多时候我们都不会像后端工程师一样重视这项能力。但事实上，算法对每一个程序员来说，都有着不可撼动的地位。
因为开发的过程就是把实际问题转换成计算机可识别的指令，也就是《数据结构》里说的，「设计出数据结构，在施加以算法就行了」。
当然，学习也是有侧重点的，作为前端我们不需要像后端开发一样对算法全盘掌握，有些比较偏、不实用的类型和解法，只要稍做了解即可。
题目🦀
难度中等
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
class Node { public int val; public List<Node> neighbors; }
测试用例格式：
简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。
邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。
示例 1：
输入：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：
输入：adjList = [[]] 输出：[[]] 解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。
示例 3：
输入：adjList = [] 输出：[] 解释：这个图是空的，它不含任何节点。
示例 4：
输入：adjList = [[2],[1]] 输出：[[2],[1]] 复制代码
提示：
- 节点数不超过 100 。
- 每个节点值
Node.val都是唯一的，1 <= Node.val <= 100。 - 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
- 由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
- 图是连通图，你可以从给定节点访问到所有节点。
解题思路🌵
- 拷贝所有节点。
- 拷贝所有的边。
解题步骤🐂
- 深度或者广度遍历所有节点。
- 拷贝所有节点，存储起来。
- 将拷贝的节点，按照原图的连接方法进行连接。
源码🔥
深度优先遍历解法
/** * // 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=>{ if(!visited.has(ne)){ dfs(ne) } nCopy.neighbors.push(visited.get(ne)) }) } dfs(node) return visited.get(node) };
时间复杂度:O(n)
空间复杂度:O(n)
广度优先遍历解法
/** * // 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(); visited.set(node,new Node(node.val)) const q=[node]; while(q.length){ const n=q.shift(); console.log(n.val); (n.neighbors||[]).forEach(item=>{ if(!visited.has(item)){ q.push(item) const nCopy=new Node(item.val); visited.set(item,nCopy); } visited.get(n).neighbors.push(visited.get(item)) }) } return visited.get(node) };
结束语🌞
那么鱼鱼的LeetCode算法篇的「LeetCode」133-克隆图⚡️ 就结束了，算法这个东西没有捷径，只能多写多练，多总结，文章的目的其实很简单，就是督促自己去完成算法练习并总结和输出，菜不菜不重要，但是热爱🔥，喜欢大家能够喜欢我的短文，也希望通过文章认识更多志同道合的朋友，如果你也喜欢折腾，欢迎加我好友，一起沙雕，一起进步。
