做网站 租服务器吗,网络舆情参考,专门做酒的网站,北京企业建设网站公司一文了解图在前端中的应用#x1f3a7;序言#x1f3a4;一、图是什么#xff1f;1、定义2、举例#x1f3b9;二、图的表示法1、邻接矩阵表示法2、邻接表表示法#x1f3ba;三、图的常用操作1、图的深度优先遍历#xff08;1#xff09;定义#xff08;2#xff09;口诀… 一文了解图在前端中的应用序言一、图是什么1、定义2、举例二、图的表示法1、邻接矩阵表示法2、邻接表表示法三、图的常用操作1、图的深度优先遍历1定义2口诀3代码实现2、图的广度优先遍历1定义2口诀3代码实现四、leetcode经典题目解析1、leetcode417太平洋大西洋水流问题中等2、leetcode133克隆图中等3、leetcode65有效数字困难五、结束语彩蛋时间Painted Eggshell往期推荐番外篇序言
在我们的日常生活中图无处不在。小到一张小小地图大到我们我们乘坐的航班每一个都跟图有着紧密的联系。
而对于前端来说图的应用也是相对比较广泛的。图常用于克隆图、太平洋大西洋水流问题、有效数字的判断等等场景。
在下面的这篇文章中将讲解关于图的一些基础知识以及图在前端中的常见应用。
一起来学习吧~☂️
一、图是什么
1、定义
图是由顶点的集合和边的集合组成的。图是网络结构的抽象模型是一组由边连接的节点。图可以表示任何二元关系比如道路、航班……。JS 中没有图但是可以用 Object 和 Array 构建图。图的表示法领接矩阵、邻接表、关联矩阵……
2、举例
地铁线路中每一个站点可以看成是一个顶点而连接着每个站点的线路可以看做是边。
二、图的表示法
图通常有两种表示法领接矩阵和邻接表。下面一起来看这两种表示法~
1、邻接矩阵表示法
下面用一张图来展示邻接矩阵的表示法。详情见下图 2、邻接表表示法
大家可以看到上面的邻接矩阵在矩阵中存在着大量的0这将会占据程序中大量的内存。因此我们引入了邻接表来解决这个问题。详情见下图 三、图的常用操作
1、图的深度优先遍历
1定义
图的深度优先遍历即尽可能深的搜索图的分支。
2口诀
访问根节点。对根节点没访问过的相邻节点挨个进行深度优先遍历。
3代码实现
接下来我们用 JS 来实现图的深度优先遍历这里我们采用邻接表的形式来表示。具体代码如下
我们先来定义一个图的结构
const graph {0:[1, 2],1:[2],2:[0, 3],3:[3]
}接下来来对这个结构进行深度优先遍历
const visited new Set();const dfs (n) { console.log(n);//将访问过的节点加入集合中visited.add(n);//对当前节点所对应的数组挨个进行遍历graph[n].forEach(c {// 对没有访问过的在此访问if(!visited.has(c)){//递归进行深度遍历dfs(c);}})
}
//以2为起始点进行深度优先遍历
dfs(2);最后我们来看下打印结果
/*打印结果
2
0
1
3
*/2、图的广度优先遍历
1定义
图的广度优先遍历先访问离根节点最近的节点。
2口诀
新建一个队列把根节点入队。把队头出队并访问。把队头每访问过的相邻节点入队。重复第二、三步操作直到队列为空。
3代码实现
接下来我们用 JS 来实现图的广度优先遍历这里我们采用邻接表的形式来表示。具体代码如下
同样地我们先来定义一个图的结构
const graph {0:[1, 2],1:[2],2:[0, 3],3:[3]
}接下来来对这个结构进行深度优先遍历
//新建一个集合存放访问过的节点
const visited new Set();
//初始节点放进集合中
visited.add(2);
//将初始节点放入队列q中
const q [2];while(q.length){//删除队列q的第一个元素并将其值返回const n q.shift();//打印返回后的值console.log(n);//将该值所对应邻接表的数组挨个进行遍历graph[n].forEach(c {//判断数组中的元素是否已经访问过if(!visited.has(c)){//如果没有访问过则加入访问队列和访问集合q.push(c);visited.add(c);}});
}最后我们来看下打印结果
/*打印结果
2
0
3
1
*/四、leetcode经典题目解析
接下来我们引用几道经典的 leetcode 算法来巩固图的知识。
温馨小提示 题意的内容范例是对官方题目的简单概要并不是特别全面建议大家先点击链接查看使用体验更为友好~
1、leetcode417太平洋大西洋水流问题中等
1题意
附上题目链接leetcode417太平洋大西洋水流问题
给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界而“大西洋”处于大陆的右边界和下边界。
规定水流只能按照上、下、左、右四个方向流动且只能从高到低或者在同等高度上流动。
请找出那些水流既可以流动到“太平洋”又能流动到“大西洋”的陆地单元的坐标。
提示
输出坐标的顺序不重要m 和 n 都小于150
输入输出示例 给定下面的 5x5 矩阵:太平洋 ~ ~ ~ ~ ~ ~ 1 2 2 3 (5) *~ 3 2 3 (4) (4) *~ 2 4 (5) 3 1 *~ (6) (7) 1 4 5 *~ (5) 1 1 2 4 ** * * * * 大西洋返回:[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
2解题思路
把矩阵想象成图。从海岸线逆流而上遍历图所到之处就是可以留到某个大洋的坐标。
3解题步骤
新建两个矩阵分别记录能留到两个大洋的坐标。从海岸线多管旗下同时深度优先遍历图过程中填充上述矩阵。遍历两个矩阵找出能流到两个大洋的坐标。
4代码实现
/*** param {number[][]} matrix* return {number[][]}*/let pacificAtlantic function(matrix) {// 如果传入的不是一个矩阵则返回一个空数组if(!matrix !matrix[0]){return [];}// m表示矩阵的行数n表示矩阵的列数const m matrix.length;// matrix[0]表示矩阵的第一行const n matrix[0].length;// 定义flow1记录留到太平洋的坐标flow2记录留到大西洋的坐标// from方法构建长度为m的数组,第二个参数填充指定数组的值填充为什么样const flow1 Array.from({length: m}, () new Array(n).fill(false));const flow2 Array.from({length: m}, () new Array(n).fill(false));// console.log(flow1);// console.log(flow2);// 进行深度优先遍历// r即row,表示行c即column表示列// flow为二维数组const dfs (r, c, flow) {flow[r][c] true;[[r -1, c],[r 1, c],[r, c - 1], [r, c 1]].forEach(([nr,nc]) {if(// 保证在矩阵中nr 0 nr m nc 0 nc n // 防止死循环!flow[nr][nc] // 保证逆流而上即保证下一个节点的值大于上一个节点的值matrix[nr][nc] matrix[r][c]){dfs(nr, nc, flow);}});};// 沿着海岸线逆流而上for(let r 0; r m; r){//第一列的流到太平洋即flow1dfs(r, 0, flow1);//最后一列的留到大西洋即flow2dfs(r, n - 1, flow2);}for(let c 0; c n; c){//第一行的流到太平洋即flow1dfs(0, c, flow1);//最后一行的留到大西洋即flow2dfs(m - 1, c, flow2);}//收集能留到两个大洋里的坐标const res [];for(let r 0; r m; r){for(let c 0; c n; c){//当flow1和flow2都为true时则说明既能留到太平洋也能流到大西洋if(flow1[r][c] flow2[r][c]){res.push([r, c]);}}}return res;
};
console.log(pacificAtlantic([[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]))/*打印结果
[[ 0, 4 ], [ 1, 3 ],[ 1, 4 ], [ 2, 2 ],[ 3, 0 ], [ 3, 1 ],[ 4, 0 ]
]
*/2、leetcode133克隆图中等
1题意
附上题目链接leetcode133克隆图
给你无向 连通 图中一个节点的引用请你返回该图的 深拷贝克隆。
图中的每个节点都包含它的值 valint 和其邻居的列表list[Node]。
class Node {public int val;public ListNode neighbors;
}输入输出示例
输入: 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解题思路
拷贝所有节点。拷贝所有的边。
3解题步骤
深度或广度优先遍历所有节点。拷贝所有的结点存储起来。将拷贝的结点按照原图的连接方法进行连接。
4代码实现
我们用两种方式来实现克隆图深度优先遍历和广度优先遍历。具体代码如下
深度优先遍历
/*** // Definition for a Node.* function Node(val, neighbors) {* this.val val undefined ? 0 : val;* //邻居节点是一个数组* this.neighbors neighbors undefined ? [] : neighbors;* };*//*** param {Node} node* return {Node}*/
// 深度优先遍历
let cloneGraph1 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上nCopy.neighbors.push(visited.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}*/
let cloneGraph2 function(node) {//如果当前节点为空则直接返回if(!node){return;}//定义一个字典存放访问过的节点const visited new Map();//visited存放节点以及节点的值visited.set(node, new Node(node.val));// 初始化一个队列const q [node];// 当队列内有节点信息时while(q.length){// 删除队列中的第一个元素并返回值const n q.shift();//将节点的邻居挨个进行遍历(n.neighbors || []).forEach(ne {// 判断访问队列是否有过邻居节点if(!visited.has(ne)){// 将节点的邻居加入到队列中q.push(ne);// 将节点的邻居及邻居的值放入visited中visited.set(ne, new Node(ne.val));}/*如果访问队列已经有过该节点则将此节点放入访问队列的邻居节点*/visited.get(n).neighbors.push(visited.get(ne));});}//返回访问队列的节点信息return visited.get(node);
};3、leetcode65有效数字困难
1题意
附上题目链接leetcode65有效数字
有效数字按顺序可以分成以下几个部分
一个 小数 或者 整数可选一个 e 或 E 后面跟着一个 整数
小数按顺序可以分成以下几个部分 可选一个符号字符 或 - 下述格式之一 至少一位数字后面跟着一个点 .至少一位数字后面跟着一个点 . 后面再跟着至少一位数字一个点 . 后面跟着至少一位数字
整数按顺序可以分成以下几个部分
可选一个符号字符 或 -至少一位数字
输入输出示例
输入: s “0”输出: true
2解题思路-图例 3解题步骤
构建一个表示状态的图。遍历字符串并沿着图走如果到了某个节点无路可走就返回false。遍历结束如走到3/5/6就返回true否则返回false。
4代码实现
let isNumber function(s){const graph {0:{blank: 0, sign: 1, .: 2, digit: 6 },1:{digit: 6, .: 2 },2:{digit: 3 },3:{digit: 3, e: 4 },4:{digit: 5, sign: 7 },5:{digit: 5 },6:{digit: 6, .: 3, e: 4 },7:{digit: 5 }}let state 0;for(c of s.trim()){if(c 0 c 9){c digit;}else if(c ){c blank;}else if(c || c -){c sign;}state graph[state][c];if(state undefined){return false;}}if(state 3 || state 5 || state 6){return true;}return false;
}五、结束语
通过上文的学习我们了解到了图的两种表示法邻接矩阵表示法和邻接表表示法。同时还学习了图的两种常用操作图的深度优先遍历和图的广度优先遍历。最后我们引用了几道 leetcode 算法题来解决了图的一些常用场景。
个人认为图相对于其他数据结构来说学习难度更大一点但又是一个不得不学的基本知识所以还是得多加练习。
除此之外呢对于以上算法题学有余力之余可以考虑多调试一步步跟着调试走慢慢的就理解的更透彻了。
关于图在前端中的应用讲到这里就结束啦希望对大家有帮助~
如有疑问或文章有误欢迎评论区留言或公众号后台加我微信提问~
彩蛋时间Painted Eggshell
往期推荐
栈栈在前端中的应用顺便再了解下深拷贝和浅拷贝
队列详解队列在前端的应用深剖JS中的事件循环Eventloop再了解微任务和宏任务
链表详解链表在前端的应用顺便再弄懂原型和原型链
字典和集合ES6的Set和Map你都知道吗一文了解集合和字典在前端中的应用
树一文了解树在前端中的应用掌握数据结构中树的生命线
动态规则和分而治之算法一文了解分而治之和动态规则算法在前端中的应用
贪心算法和回溯算法一文了解贪心算法和回溯算法在前端中的应用
番外篇 关注公众号星期一研究室第一时间关注学习干货更多精选专栏待你解锁~如果这篇文章对你有用记得留个脚印jio再走哦~以上就是本文的全部内容我们下期见
