一文了解圖在前端中的應(yīng)用

• 🎧序言
• 🎤一、圖是什么？
• • 1、定義
  • 2、舉例
• 🎹二、圖的表示法
• • 1、鄰接矩陣表示法
  • 2、鄰接表表示法
• 🎺三、圖的常用操作
• • 1、圖的深度優(yōu)先遍歷
  • • （1）定義
    • （2）口訣
    • （3）代碼實(shí)現(xiàn)
  • 2、圖的廣度優(yōu)先遍歷
  • • （1）定義
    • （2）口訣
    • （3）代碼實(shí)現(xiàn)
• 🎻四、leetcode經(jīng)典題目解析
• • 1、leetcode417太平洋大西洋水流問(wèn)題（中等）
  • 2、leetcode133克隆圖（中等）
  • 3、leetcode65有效數(shù)字（困難）
• 🎸五、結(jié)束語(yǔ)
• 🐣彩蛋時(shí)間Painted Eggshell
• • 往期推薦
  • 番外篇

🎧序言

在我們的日常生活中，圖無(wú)處不在。小到一張小小地圖，大到我們我們乘坐的航班，每一個(gè)都跟圖有著緊密的聯(lián)系。

而對(duì)于前端來(lái)說(shuō)，圖的應(yīng)用也是相對(duì)比較廣泛的。圖常用于克隆圖、太平洋大西洋水流問(wèn)題、有效數(shù)字的判斷等等場(chǎng)景。

在下面的這篇文章中，將講解關(guān)于圖的一些基礎(chǔ)知識(shí)，以及圖在前端中的常見(jiàn)應(yīng)用。

一起來(lái)學(xué)習(xí)吧~??

🎤一、圖是什么？

1、定義

• 圖是由頂點(diǎn)的集合和邊的集合組成的。
• 圖是網(wǎng)絡(luò)結(jié)構(gòu)的抽象模型，是一組由邊連接的節(jié)點(diǎn)。
• 圖可以表示任何二元關(guān)系，比如道路、航班……。
• JS 中沒(méi)有圖，但是可以用 Object 和 Array 構(gòu)建圖。
• 圖的表示法：領(lǐng)接矩陣、鄰接表、關(guān)聯(lián)矩陣……

2、舉例

地鐵線路中每一個(gè)站點(diǎn)可以看成是一個(gè)頂點(diǎn)，而連接著每個(gè)站點(diǎn)的線路可以看做是邊。

🎹二、圖的表示法

圖通常有兩種表示法：領(lǐng)接矩陣和鄰接表。下面一起來(lái)看這兩種表示法~

1、鄰接矩陣表示法

下面用一張圖來(lái)展示鄰接矩陣的表示法。詳情見(jiàn)下圖👇

2、鄰接表表示法

大家可以看到上面的鄰接矩陣，在矩陣中存在著大量的0，這將會(huì)占據(jù)程序中大量的內(nèi)存。因此，我們引入了鄰接表，來(lái)解決這個(gè)問(wèn)題。詳情見(jiàn)下圖👇

🎺三、圖的常用操作

1、圖的深度優(yōu)先遍歷

（1）定義

• 圖的深度優(yōu)先遍歷，即盡可能深的搜索圖的分支。

（2）口訣

• 訪問(wèn)根節(jié)點(diǎn)。
• 對(duì)根節(jié)點(diǎn)沒(méi)訪問(wèn)過(guò)的相鄰節(jié)點(diǎn)挨個(gè)進(jìn)行深度優(yōu)先遍歷。

（3）代碼實(shí)現(xiàn)

接下來(lái)我們用 JS 來(lái)實(shí)現(xiàn)圖的深度優(yōu)先遍歷，這里我們采用鄰接表的形式來(lái)表示。具體代碼如下：

我們先來(lái)定義一個(gè)圖的結(jié)構(gòu)：

const graph = {0:[1, 2],1:[2],2:[0, 3],3:[3] }

接下來(lái)來(lái)對(duì)這個(gè)結(jié)構(gòu)進(jìn)行深度優(yōu)先遍歷：

const visited = new Set();const dfs = (n) => { console.log(n);//將訪問(wèn)過(guò)的節(jié)點(diǎn)加入集合中visited.add(n);//對(duì)當(dāng)前節(jié)點(diǎn)所對(duì)應(yīng)的數(shù)組挨個(gè)進(jìn)行遍歷graph[n].forEach(c => {// 對(duì)沒(méi)有訪問(wèn)過(guò)的在此訪問(wèn)if(!visited.has(c)){//遞歸進(jìn)行深度遍歷dfs(c);}}) } //以2為起始點(diǎn)進(jìn)行深度優(yōu)先遍歷 dfs(2);

最后我們來(lái)看下打印結(jié)果：

/*打印結(jié)果： 2 0 1 3 */

2、圖的廣度優(yōu)先遍歷

（1）定義

• 圖的廣度優(yōu)先遍歷，先訪問(wèn)離根節(jié)點(diǎn)最近的節(jié)點(diǎn)。

（2）口訣

• 新建一個(gè)隊(duì)列，把根節(jié)點(diǎn)入隊(duì)。
• 把隊(duì)頭出隊(duì)并訪問(wèn)。
• 把隊(duì)頭每訪問(wèn)過(guò)的相鄰節(jié)點(diǎn)入隊(duì)。
• 重復(fù)第二、三步操作，直到隊(duì)列為空。

（3）代碼實(shí)現(xiàn)

接下來(lái)我們用 JS 來(lái)實(shí)現(xiàn)圖的廣度優(yōu)先遍歷，這里我們采用鄰接表的形式來(lái)表示。具體代碼如下：

同樣地我們先來(lái)定義一個(gè)圖的結(jié)構(gòu)：

const graph = {0:[1, 2],1:[2],2:[0, 3],3:[3] }

接下來(lái)來(lái)對(duì)這個(gè)結(jié)構(gòu)進(jìn)行深度優(yōu)先遍歷：

//新建一個(gè)集合，存放訪問(wèn)過(guò)的節(jié)點(diǎn) const visited = new Set(); //初始節(jié)點(diǎn)放進(jìn)集合中 visited.add(2); //將初始節(jié)點(diǎn)放入隊(duì)列q中 const q = [2];while(q.length){//刪除隊(duì)列q的第一個(gè)元素，并將其值返回const n = q.shift();//打印返回后的值console.log(n);//將該值所對(duì)應(yīng)鄰接表的數(shù)組，挨個(gè)進(jìn)行遍歷graph[n].forEach(c => {//判斷數(shù)組中的元素是否已經(jīng)訪問(wèn)過(guò)if(!visited.has(c)){//如果沒(méi)有訪問(wèn)過(guò)則加入訪問(wèn)隊(duì)列和訪問(wèn)集合q.push(c);visited.add(c);}}); }

最后我們來(lái)看下打印結(jié)果：

/*打印結(jié)果： 2 0 3 1 */

🎻四、leetcode經(jīng)典題目解析

接下來(lái)我們引用幾道經(jīng)典的 leetcode 算法，來(lái)鞏固圖的知識(shí)。

溫馨小提示： 題意的內(nèi)容范例是對(duì)官方題目的簡(jiǎn)單概要，并不是特別全面，建議大家先點(diǎn)擊鏈接查看，使用體驗(yàn)更為友好~

1、leetcode417太平洋大西洋水流問(wèn)題（中等）

（1）題意

附上題目鏈接：leetcode417太平洋大西洋水流問(wèn)題

給定一個(gè) m x n 的非負(fù)整數(shù)矩陣來(lái)表示一片大陸上各個(gè)單元格的高度。“太平洋”處于大陸的左邊界和上邊界，而“大西洋”處于大陸的右邊界和下邊界。

規(guī)定水流只能按照上、下、左、右四個(gè)方向流動(dòng)，且只能從高到低或者在同等高度上流動(dòng)。

請(qǐng)找出那些水流既可以流動(dòng)到“太平洋”，又能流動(dòng)到“大西洋”的陸地單元的坐標(biāo)。

提示：

• 輸出坐標(biāo)的順序不重要
• 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]] (上圖中帶括號(hào)的單元).

（2）解題思路

• 把矩陣想象成圖。
• 從海岸線逆流而上遍歷圖，所到之處就是可以留到某個(gè)大洋的坐標(biāo)。

（3）解題步驟

• 新建兩個(gè)矩陣，分別記錄能留到兩個(gè)大洋的坐標(biāo)。
• 從海岸線，多管旗下，同時(shí)深度優(yōu)先遍歷圖，過(guò)程中填充上述矩陣。
• 遍歷兩個(gè)矩陣，找出能流到兩個(gè)大洋的坐標(biāo)。

（4）代碼實(shí)現(xiàn)

/*** @param {number[][]} matrix* @return {number[][]}*/let pacificAtlantic = function(matrix) {// 如果傳入的不是一個(gè)矩陣，則返回一個(gè)空數(shù)組if(!matrix && !matrix[0]){return [];}// m表示矩陣的行數(shù)，n表示矩陣的列數(shù)const m = matrix.length;// matrix[0]表示矩陣的第一行const n = matrix[0].length;// 定義flow1記錄留到太平洋的坐標(biāo)，flow2記錄留到大西洋的坐標(biāo)// from方法構(gòu)建長(zhǎng)度為m的數(shù)組,第二個(gè)參數(shù)填充指定數(shù)組的值填充為什么樣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);// 進(jìn)行深度優(yōu)先遍歷// r即row,表示行；c即column，表示列// flow為二維數(shù)組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 &&// 防止死循環(huán)!flow[nr][nc] &&// 保證逆流而上，即保證下一個(gè)節(jié)點(diǎn)的值大于上一個(gè)節(jié)點(diǎn)的值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);}//收集能留到兩個(gè)大洋里的坐標(biāo)const res = [];for(let r = 0; r < m; r++){for(let c = 0; c < n; c++){//當(dāng)flow1和flow2都為true時(shí)，則說(shuō)明既能留到太平洋，也能流到大西洋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]]))/*打印結(jié)果： [[ 0, 4 ], [ 1, 3 ],[ 1, 4 ], [ 2, 2 ],[ 3, 0 ], [ 3, 1 ],[ 4, 0 ] ] */

2、leetcode133克隆圖（中等）

（1）題意

附上題目鏈接：leetcode133克隆圖

給你無(wú)向 連通 圖中一個(gè)節(jié)點(diǎn)的引用，請(qǐng)你返回該圖的 深拷貝（克隆）。

圖中的每個(gè)節(jié)點(diǎn)都包含它的值 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 個(gè)節(jié)點(diǎn)。
  • 節(jié)點(diǎn) 1 的值是 1，它有兩個(gè)鄰居：節(jié)點(diǎn) 2 和 4 。
  • 節(jié)點(diǎn) 2 的值是 2，它有兩個(gè)鄰居：節(jié)點(diǎn) 1 和 3 。
  • 節(jié)點(diǎn) 3 的值是 3，它有兩個(gè)鄰居：節(jié)點(diǎn) 2 和 4 。
  • 節(jié)點(diǎn) 4 的值是 4，它有兩個(gè)鄰居：節(jié)點(diǎn) 1 和 3 。

（2）解題思路

• 拷貝所有節(jié)點(diǎn)。
• 拷貝所有的邊。

（3）解題步驟

• 深度或廣度優(yōu)先遍歷所有節(jié)點(diǎn)。
• 拷貝所有的結(jié)點(diǎn)，存儲(chǔ)起來(lái)。
• 將拷貝的結(jié)點(diǎn)，按照原圖的連接方法進(jìn)行連接。

（4）代碼實(shí)現(xiàn)

我們用兩種方式來(lái)實(shí)現(xiàn)克隆圖：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。具體代碼如下：

深度優(yōu)先遍歷：

/*** // Definition for a Node.* function Node(val, neighbors) {* this.val = val === undefined ? 0 : val;* //鄰居節(jié)點(diǎn)是一個(gè)數(shù)組* this.neighbors = neighbors === undefined ? [] : neighbors;* };*//*** @param {Node} node* @return {Node}*/ // 深度優(yōu)先遍歷 let cloneGraph1 = function(node) {//如果當(dāng)前節(jié)點(diǎn)為空，則直接返回if(!node){return;}//定義一個(gè)字典，存放訪問(wèn)過(guò)的節(jié)點(diǎn)const visited = new Map();//深度優(yōu)先遍歷const dfs = (n) => {// 拷貝一份當(dāng)前初始節(jié)點(diǎn)的值const nCopy = new Node(n.val);//將拷貝后的節(jié)點(diǎn)放到訪問(wèn)字典當(dāng)中visited.set(n, nCopy);//對(duì)初始節(jié)點(diǎn)的鄰居節(jié)點(diǎn)挨個(gè)進(jìn)行遍歷(n.neighbors || []).forEach(ne => {//判斷訪問(wèn)隊(duì)列是否有過(guò)鄰居節(jié)點(diǎn)if(!visited.has(ne)){/* 如果訪問(wèn)隊(duì)列沒(méi)有過(guò)該鄰居節(jié)點(diǎn)，則將鄰居節(jié)點(diǎn)繼續(xù)進(jìn)行深度遍歷*/dfs(ne);}// 將訪問(wèn)過(guò)的鄰居節(jié)點(diǎn)的值拷貝到nCopy上nCopy.neighbors.push(visited.get(ne));});};dfs(node);return visited.get(node); };

廣度優(yōu)先遍歷：

/*** // Definition for a Node.* function Node(val, neighbors) {* this.val = val === undefined ? 0 : val;* //鄰居節(jié)點(diǎn)是一個(gè)數(shù)組* this.neighbors = neighbors === undefined ? [] : neighbors;* };*//*** @param {Node} node* @return {Node}*/ let cloneGraph2 = function(node) {//如果當(dāng)前節(jié)點(diǎn)為空，則直接返回if(!node){return;}//定義一個(gè)字典，存放訪問(wèn)過(guò)的節(jié)點(diǎn)const visited = new Map();//visited存放節(jié)點(diǎn)以及節(jié)點(diǎn)的值visited.set(node, new Node(node.val));// 初始化一個(gè)隊(duì)列const q = [node];// 當(dāng)隊(duì)列內(nèi)有節(jié)點(diǎn)信息時(shí)while(q.length){// 刪除隊(duì)列中的第一個(gè)元素并返回值const n = q.shift();//將節(jié)點(diǎn)的鄰居挨個(gè)進(jìn)行遍歷(n.neighbors || []).forEach(ne => {// 判斷訪問(wèn)隊(duì)列是否有過(guò)鄰居節(jié)點(diǎn)if(!visited.has(ne)){// 將節(jié)點(diǎn)的鄰居加入到隊(duì)列中q.push(ne);// 將節(jié)點(diǎn)的鄰居及鄰居的值放入visited中visited.set(ne, new Node(ne.val));}/*如果訪問(wèn)隊(duì)列已經(jīng)有過(guò)該節(jié)點(diǎn)，則將此節(jié)點(diǎn)放入訪問(wèn)隊(duì)列的鄰居節(jié)點(diǎn)*/visited.get(n).neighbors.push(visited.get(ne));});}//返回訪問(wèn)隊(duì)列的節(jié)點(diǎn)信息return visited.get(node); };

3、leetcode65有效數(shù)字（困難）

（1）題意

附上題目鏈接：leetcode65有效數(shù)字

有效數(shù)字（按順序）可以分成以下幾個(gè)部分：

• 一個(gè) 小數(shù) 或者 整數(shù)
• （可選）一個(gè) 'e' 或 'E' ，后面跟著一個(gè) 整數(shù)

小數(shù)（按順序）可以分成以下幾個(gè)部分：

• （可選）一個(gè)符號(hào)字符（'+' 或 '-'）

• 下述格式之一：

  • 至少一位數(shù)字，后面跟著一個(gè)點(diǎn) '.'
  • 至少一位數(shù)字，后面跟著一個(gè)點(diǎn) '.' ，后面再跟著至少一位數(shù)字
  • 一個(gè)點(diǎn) '.' ，后面跟著至少一位數(shù)字

整數(shù)（按順序）可以分成以下幾個(gè)部分：

• （可選）一個(gè)符號(hào)字符（'+' 或 '-'）
• 至少一位數(shù)字

輸入輸出示例：

• 輸入: s = “0”
• 輸出: true

（2）解題思路-圖例

（3）解題步驟

• 構(gòu)建一個(gè)表示狀態(tài)的圖。
• 遍歷字符串，并沿著圖走，如果到了某個(gè)節(jié)點(diǎn)無(wú)路可走就返回false。
• 遍歷結(jié)束，如走到3/5/6，就返回true，否則返回false。

（4）代碼實(shí)現(xiàn)

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; }

🎸五、結(jié)束語(yǔ)

通過(guò)上文的學(xué)習(xí)，我們了解到了圖的兩種表示法：鄰接矩陣表示法和鄰接表表示法。同時(shí)，還學(xué)習(xí)了圖的兩種常用操作：圖的深度優(yōu)先遍歷和圖的廣度優(yōu)先遍歷。最后，我們引用了幾道 leetcode 算法題，來(lái)解決了圖的一些常用場(chǎng)景。

個(gè)人認(rèn)為，圖相對(duì)于其他數(shù)據(jù)結(jié)構(gòu)來(lái)說(shuō)，學(xué)習(xí)難度更大一點(diǎn)，但又是一個(gè)不得不學(xué)的基本知識(shí)，所以還是得多加練習(xí)。

除此之外呢，對(duì)于以上算法題，學(xué)有余力之余，可以考慮多調(diào)試，一步步跟著調(diào)試走，慢慢的就理解的更透徹了。

關(guān)于圖在前端中的應(yīng)用講到這里就結(jié)束啦！希望對(duì)大家有幫助~

如有疑問(wèn)或文章有誤歡迎評(píng)論區(qū)留言或公眾號(hào)后臺(tái)加我微信提問(wèn)~

🐣彩蛋時(shí)間Painted Eggshell

往期推薦

棧👉棧在前端中的應(yīng)用，順便再了解下深拷貝和淺拷貝！

隊(duì)列👉詳解隊(duì)列在前端的應(yīng)用，深剖JS中的事件循環(huán)Eventloop，再了解微任務(wù)和宏任務(wù)

鏈表👉詳解鏈表在前端的應(yīng)用，順便再弄懂原型和原型鏈！

字典和集合👉ES6的Set和Map你都知道嗎？一文了解集合和字典在前端中的應(yīng)用

樹(shù)👉一文了解樹(shù)在前端中的應(yīng)用，掌握數(shù)據(jù)結(jié)構(gòu)中樹(shù)的生命線

動(dòng)態(tài)規(guī)則和分而治之算法👉一文了解分而治之和動(dòng)態(tài)規(guī)則算法在前端中的應(yīng)用

貪心算法和回溯算法👉一文了解貪心算法和回溯算法在前端中的應(yīng)用

番外篇

• 關(guān)注公眾號(hào)星期一研究室，第一時(shí)間關(guān)注學(xué)習(xí)干貨，更多精選專欄待你解鎖~
• 如果這篇文章對(duì)你有用，記得留個(gè)腳印jio再走哦~
• 以上就是本文的全部?jī)?nèi)容！我們下期見(jiàn)！👋👋👋

總結(jié)

以上是生活随笔為你收集整理的太平洋大西洋水流问题如何解决？一文了解图在前端中的应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。