图和广度优先搜索

你经常要找出最短路径，这可能是前往朋友家的最短路径，也可能是国际象棋中把对方将死的最少步数。解决最短路径问题的算法被称为广度优先搜索
需要两个步骤
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);
};