🎤一、图是什么？
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++){ //第一列的流到太平洋，即flow1 dfs(r, 0, flow1); //最后一列的留到大西洋，即flow2 dfs(r, n - 1, flow2); } for(let c = 0; c < n; c++){ //第一行的流到太平洋，即flow1 dfs(0, c, flow1); //最后一行的留到大西洋，即flow2 dfs(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克隆图
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
class Node { public int val; public List<Node> 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
（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 算法题，来解决了图的一些常用场景。
个人认为，图相对于其他数据结构来说，学习难度更大一点，但又是一个不得不学的基本知识，所以还是得多加练习。
除此之外呢，对于以上算法题，学有余力之余，可以考虑多调试，一步步跟着调试走，慢慢的就理解的更透彻了。
关于图在前端中的应用讲到这里就结束啦！希望对大家有帮助~
