你经常要找出最短路径，这可能是前往朋友家的最短路径，也可能是国际象棋中把对方将死的最少步数。解决最短路径问题的算法被称为广度优先搜索
需要两个步骤
1). 使用图来构建问题模型。
2). 使用广度优先搜索解决问题。
1. 是什么
- 网络结构的抽象模型，是一组由边连接的节点。
- 用于模拟不同的东西是如何相连的。
- js 里可以用 Object 和 Array 构建图。
- 图的表示法：邻接矩阵、邻接表。关联矩阵......
1.1. 广度优先搜索
- 一种用于图的查找算法，可帮助解决两类问题
1). 从节点 A 出发，有前往节点 B 的路径吗？
2). 从节点 A 出发，前往节点 B 的哪条路径最短？
1.1.1
有路径吗？
假设你经营一个芒果农场，需要找芒果经销商，以便将芒果卖给他。在 Facebook，你与芒果销售商有联系吗？为此，你可以在朋友中查找。
然后依次检查名单中的每个人，看看他是否是芒果销售商。
假设你没有朋友是芒果销售商，那么你必须在朋友的朋友中查找。
检查名单中的每个人时，你都将其朋友加入名单。
1.1.2 查找最短路径
以上面的案例为例，广度优先搜索可回答的两类问题
- 从节点 A 出发，有前往节点 B 的路径吗？（在你的人际关系网中，有芒果销售商吗？）
- 从节点 A 出发，前往节点 B 的哪条路径最短？（哪个芒果销售商与你的关系最近？）
那么第二类哪个芒果销售商与你的关系最近
例如：朋友是一度关系，朋友的朋友是二度以此类推
我们应先在一度中搜索，如果没有才在二度中搜索。也就是一度关系在二度关系之前加入查找名单。
而我们想保证我们的查找顺序就需要用到队列
2. 图的表示法
2.1. 邻接矩阵
2.2. 邻接表
3. 常用操作
- 深度优先遍历
尽可能深的搜索图的分支。 - 广度优先遍历
先访问离根节点最近的节点。
3.1. 深度优先遍历算法口诀
- 访问根节点
- 对根节点的没访问过的相邻节点挨个进行深度优先遍历
graph.js
const graph = {
0: [1, 2],
1: [2],
2: [0, 3],
3: [3]
};
module.exports = graph;
- dfs.js
const graph = require('./graph');
const visited = new Set();
const dfs = (node) => {
console.log(node)
visited.add(node);
graph[node].forEach(c => {
if (!visited.has(c)) {
dfs(c);
}
})
};
dfs(2); // 2 0, 1, 3
从2开始首先遍历0，0遍历完了遍历0里面的1，1下面的2已经访问过了，所以不再继续遍历，开始遍历回到第一次的遍历遍历2里面的3
3.2. 广度优先遍历算法口诀
- 新建一个队列，把根节点入队。
- 把队头出队并访问。
- 把队头的没访问过的相邻节点入队。
- 重复第二三步，直到队列为空。
const graph = require('./graph');
const visited = new Set();
visited.add(2);
const q = [2];
while(q.length) {
const n = q.shift();
console.log(n);
graph[n].forEach(c => {
if (!visited.has(c)) {
q.push(c);
visited.add(c);
}
})
}
4. 场景
4.1. 有效数字 leetCode 65
上面图中左侧状态0为起点，每次都从状态0开始，并且只有3 5 6是有效的
比如第一个 "0" => true
开始的时候是0，值也是0，0-9之间的数字也就是到了左图中的6了，也就是有效的
第二个 " 0.1 " => true
从状态0开始，空格后还是状态0，然后是0到了状态6，点到了状态3，1还是状态3，后面的空格我们就可以忽略所以是true
第三个 "abc" => false
从状态0开始，第一位是a没有路可以走所以是 false
解题步骤
var isNumber = function(s) {
const graph = {
// 0通过空格是0，+/-是1，.是2，0-9是6
0: {'blank': 0, '+/-': 1, '.': 2, '0-9': 6},
1: {'0-9': 6, '.': 2},
2: { '0-9': 3 },
3: { '0-9': 3, 'e': 4 },
4: { '0-9': 5, '+/-': 7 },
5: { '0-9': 5 },
6: { '0-9': 6, '.': 3, 'e': 4 },
7: { '0-9': 5 }
};
// 起始状态为0
let state = 0;
// s.trim() 去除首尾空格，因为首尾空格不影响有效值
for (c of s.trim()) {
if (c === '') {
c = 'blank'
} else if (c === '+' || c === '-') {
c = '+/-'
} else if (c >= 0 && c <= 9) {
c = '0-9'
}
// c.toLowerCase() 'E'也是有效数字
state = graph[state][c.toLowerCase()]
if (state === undefined) {
return false;
}
}
return [3, 5, 6].includes(state);
};
4.2. 太平洋大西洋水流问题 leetCode 417
给定一个 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]] (上图中带括号的单元).
解题思路
解题步骤
var pacificAtlantic = function(heights) {
if (!heights || !heights.length) {return []}
let m = heights.length; // m 矩阵的行数
let n = heights[0].length; // n 矩阵的列数
// 能流到太平洋的矩阵（得到长度为 m 里面每一项的长度是n并且值都是 false 的矩阵，false 节点不能流入大洋里）
let flow1 = Array.from({ length: m }, () => new Array(n).fill(false));
// 能流到大西洋的矩阵
let flow2 = Array.from({ length: m }, () => new Array(n).fill(false));
// 深度遍历row: 当前节点位于第几行，col: 第几列， flow: 用到哪个 flow
const dfs = (row, col, flow) => {
// 可以流入对应大洋的设置为 true
flow[row][col] = true;
// 遍历相邻节点（上下左右四个节点）
// 上节点行数-1列数不变，下节点：行数加1列数不变，左节点：行数不变列数-1，右节点：行数不变，列数加1
[[row -1, col], [row + 1, col], [row, col -1], [row, col + 1]].forEach(([nextRow, nextCol]) => {
if (
// 保证下一个节点在矩阵中(因为m和n是length，而nextRow 和 nextCol 是 index，所以只能小于)
nextRow >= 0 && nextRow < m &&
nextCol >= 0 && nextCol < n &&
// 保证下一个节点没有访问过
!flow[nextRow][nextCol] &&
// 保证逆流而上（下一个节点大于等于上一节点）
heights[nextRow][nextCol] >= heights[row][col]
) {
dfs(nextRow, nextCol, flow)
}
})
}
// 沿着海岸线逆流而上
// 对于太平洋来说海岸线是第一行和第一列，对于大西洋来说是最后一行和最后一列
for (let row = 0; row < m; row++) {
// 太平洋：递归遍历第一列
dfs(row, 0, flow1)
// 大西洋：递归遍历最后一列
dfs(row, n - 1, flow2)
}
for (let col = 0; col < n; col++) {
// 太平洋：递归遍历第一行
dfs(0, col, flow1);
// 大西洋：递归遍历最后一行
dfs(m -1, col, flow2);
}
// 收集能同时流入两个大洋的坐标
const res = [];
for (let row = 0; row < m; row++) {
for (let col = 0; col < n; col++) {
if (flow1[row][col] && flow2[row][col]) {
res.push([row, col])
}
}
}
return res;
};
时间复杂度mn 因为最后遍历的都是 mn 个格子，空间复杂度用到了两个临时变量 flow1 和 flow2 存的都是 mn 个格子，所以空间复杂度也是mn
4.3. 克隆图 leetCode 133
解题思路
- 拷贝所有节点。
- 拷贝所有的边。
解题步骤
var cloneGraph = function(node) {
if (!node) return;
const visited = new Map();
const dfs = (n) => {
// 拷贝当前节点
const nodeCopy = new Node(n.val);
// 建立一个当前节点和拷贝后的当前节点的映射关系
visited.set(n, nodeCopy);
n.neighbors?.forEach(ne => {
if (!visited.has(ne)) {
dfs(ne)
}
nodeCopy.neighbors.push(visited.get(ne))
})
}
dfs(node);
return visited.get(node);
};
网友评论