【数据结构与算法基础】代码仓库：https://github.com/jinrunheng/datastructure-and-algorithm

一：算法笔试面试中的 BFS 问题

我们知道比起 DFS 遍历，BFS 能够解决无权图的最短路径问题。接下来我们依旧以 LeetCode 上面的问题为例，来看一下 BFS 在图论算法题中的应用。

1091. 二进制矩阵中的最短路径

如果你对求解无向图的最短路径还不太熟悉，可以先回顾一下第四章【图的广度优先遍历】中的内容。

求解无向图的最短路径，我们只能使用 BFS 遍历，像题目给定的二维矩阵，我们有两种处理方式，第一种是对二维矩阵进行图的建模，然后对建模后的图进行 bfs 求解；第二种方式类似于 FloodFill 算法一样，直接在矩阵 grid 上进行 bfs 操作。
image.png
image.png
题目要求我们返回的结果并不是真正的“最短路径”的长度，而是达成一条最短路径经过的顶点的个数，这一点还需要大家留意。

第一种方法：将二维矩阵进行图的建模

  1. class Solution {
  2.     private int[][] grid;
  3.     private int r,c;
  4.     private boolean[] visited;
  5.     private int[] dis;
  6.     private int[][] dirs = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
  7.     private HashSet<Integer>[] G;
  9.     public int shortestPathBinaryMatrix(int[][] grid) {
  11.         r = grid.length;
  12.         c = grid[0].length;
  14.         if(grid[0][0] == 1) return -1;
  15.         if(r == 1 && c == 1) return 1;
  17.         visited = new boolean[r * c];
  18.         dis = new int[r * c];
  19.         this.grid = grid;
  20.         G = constructGraph();
  21.         // bfs
  22.         Queue<Integer> q = new LinkedList<>();
  23.         q.offer(0);
  24.         visited[0] = true;
  25.         dis[0] = 1;
  27.         while(!q.isEmpty()){
  28.             int cur = q.poll();
  29.             int curX = cur / c;
  30.             int curY = cur % c;
  31.             for(int d = 0; d < 8; d++){
  32.                 int nextX = curX + dirs[d][0];
  33.                 int nextY = curY + dirs[d][1];
  34.                 int next = nextX * c + nextY;
  35.                 if(isValid(nextX,nextY) && !visited[next] && grid[nextX][nextY] == 0) {
  36.                     q.offer(next);
  37.                     visited[next] = true;
  38.                     dis[next] = dis[cur] + 1;
  39.                     if(nextX == r - 1 && nextY == c - 1) {
  40.                         return dis[next];
  41.                     }
  42.                 }
  43.             }
  44.         }
  46.         return -1;
  47.     }
  49.     private HashSet<Integer>[] constructGraph() {
  50.         HashSet<Integer>[] g = new HashSet[r * c];
  51.         for(int v = 0; v < g.length; v++)
  52.             g[v] = new HashSet<>();
  54.         for(int v = 0; v < g.length; v++) {
  55.             int x = v / c;
  56.             int y = v % c;
  57.             if(grid[x][y] == 0){
  58.                 for(int d = 0;  d < 8; d++){
  59.                     int nextX = x + dirs[d][0];
  60.                     int nextY = y + dirs[d][1];
  61.                     if(isValid(nextX,nextY) && grid[nextX][nextY] == 0) {
  62.                         int next = nextX * c + nextY;
  63.                         g[v].add(next);
  64.                         g[next].add(v);
  65.                     }
  66.                 }
  67.             }
  68.         }
  69.         return g;    
  70.     }
  72.     private boolean isValid(int x,int y){
  73.         return x >= 0 && x < r && y >= 0 && y < c;
  74.     }
  75. }

第二种方法：直接在 grid 二维数组上进行 bfs

  1. class Solution {
  3.     private int r,c;
  4.     private int[][] dirs = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
  6.     public int shortestPathBinaryMatrix(int[][] grid) {
  7.         r = grid.length;
  8.         c = grid[0].length;
  10.         if(grid[0][0] == 1) return -1;
  11.         if(r == 1 && c == 1) return 1;
  13.         boolean[][] visited = new boolean[r][c];
  14.         int[][] dis = new int[r][c];
  16.         Queue<Integer> q = new LinkedList<>();
  17.         q.offer(0);
  18.         visited[0][0] = true;
  19.         dis[0][0] = 1;
  21.         while(!q.isEmpty()){
  22.             int cur = q.poll();
  23.             int curX = cur / c;
  24.             int curY = cur % c;
  25.             if(grid[curX][curY] == 0) {
  26.                 for(int d = 0; d < 8; d++){
  27.                     int nextX = curX + dirs[d][0];
  28.                     int nextY = curY + dirs[d][1];
  29.                     if(isValid(nextX,nextY) && !visited[nextX][nextY] && grid[nextX][nextY] == 0){
  30.                         int next = nextX * c + nextY;
  31.                         q.offer(next);
  32.                         visited[nextX][nextY] = true;
  33.                         dis[nextX][nextY] = dis[curX][curY] + 1;
  34.                         if(nextX == r - 1 && nextY == c - 1)
  35.                             return dis[nextX][nextY];
  36.                     }
  37.                 }
  38.             }
  39.         }
  40.         return -1;
  41.     }
  43.     private boolean isValid(int x,int y){
  44.         return x >= 0 && x < r && y >= 0 && y < c;
  45.     }
  46. }

我们看到，同样是 BFS 遍历，第二种方式较第一种方式要好很多。

二：转盘锁问题

现在让我们看一下 LeetCode 上的第 752 号问题：752. 打开转盘锁

对于这道题目，看似和图论没有任何的关系，但是其本质就是求解无权图的最短路径。我们之前接触到的几个问题，都可以很明显地和图论联系起来，但是这个问题我们该如何构建图的模型呢？

题目给定了一个字符串 target，代表可以解锁的数字，锁的初始数字为 “0000”，一个代表四个拨轮的数字的字符串；我们每次可以旋转一个拨轮的一位数字，旋转规则题目已经给出了。

我们将每一次拨动后的状态作为图的一个顶点，从一个状态到达另一个状态记作一条边，题目出了给定解锁的数字 target 还给定了一个列表 deadends，deadends 数组中锁的状态即不构成一条边。

如下面的示例：

image.png
“6666” 是 target 值，”0901” 是 deadends 数组中的一个值，我们可以看到，每次旋转一个拨轮后的状态即可以表示为这个图的一个顶点，这个问题的本质就是求解从 “0000” 这个顶点到 “6666” 这个顶点的最短路径。

代码如下：

  1. class Solution {
  2.     public int openLock(String[] deadends, String target) {
  3.         HashSet<String> deadset = new HashSet<>();
  4.         for(String deadend : deadends)
  5.             deadset.add(deadend);
  7.         if(deadset.contains("0000")) return -1;
  8.         if(deadset.contains(target)) return -1;
  9.         if(target.equals("0000")) return 0;
  11.         // BFS
  12.         // visited key:字符串是否被遍历过，value:如果字符串被遍历过，value 存储从 "0000" 到该字符串的路径长度
  13.         HashMap<String,Integer> visited = new HashMap<>();
  14.         Queue<String> q = new LinkedList<>();
  15.         q.offer("0000");
  16.         visited.put("0000",0);
  18.         while(!q.isEmpty()){
  19.             String cur = q.poll();
  20.             List<String> nexts = getNexts(cur);
  21.             for(String next : nexts) {
  22.                 if(!deadset.contains(next) && !visited.containsKey(next)){
  23.                     q.offer(next);
  24.                     visited.put(next,visited.get(cur) + 1);
  25.                     if(next.equals(target))
  26.                         return visited.get(next);
  27.                 }
  28.             }
  29.         }
  30.         return -1;
  31.     }
  33.     private List<String> getNexts(String s){
  34.         List<String> res = new ArrayList<>();
  35.         char[] chars = s.toCharArray();
  36.         for(int i = 0; i < chars.length; i++){
  37.             char o = chars[i];
  38.             chars[i] = Character.forDigit((chars[i] - '0' + 1) % 10,10);
  39.             res.add(new String(chars));
  40.             chars[i] = o;
  41.             chars[i] = Character.forDigit((chars[i] - '0' + 9) % 10,10);
  42.             res.add(new String(chars));
  43.             chars[i] = o;
  44.         }
  45.         return res;
  46.     }
  47. }

四：Water Puzzle

Water Puzzle

有两个没有刻度的桶，一个可以盛装 5 升的水，一个可以盛装 3 升的水，问：如何利用这两个桶得到 4 升水？

image.png
这个问题想必大家都有接触过。这道智力题的解决步骤如下：

  1. 将 5L 的桶倒满水，然后倒进 3L 的桶中，这样 3L 的桶装满了水，5L 的桶中还剩下 2L 的水；
  2. 将 3L 的桶里面的水倒掉，5L 的桶里面 2L 的水倒进 3 L 桶中；
  3. 将 5L 的桶倒满水，然后往 3L 的桶里面倒水，直至 3L 的桶被倒满，此时 5L 桶中就正好盛装了 4L 的水。

其实，Water Puzzle 也可以将其转化为一个图论领域的无向图最短路径问题，进而使用 BFS 来解决。那么，这样一个问题该如何对其进行图的建模呢？和转盘锁问题类似，Water Puzzle 也是使用状态表达来标记图中的一个顶点的：

image.png
如上图所示，X，Y 分别代表 5L 的桶所盛的水和 3L 的桶所盛的水。我们从 (X,Y) 这个状态到下一个状态有三种变化方法：

  • 第一种是将 5L 桶接满，或者是将 3L 桶接满
  • 第二种是将 5L 桶清空，或者是将 3L 桶清空
  • 第三种是将 5L 桶的水倒向 3L 的桶中，或者是将 3L 桶的水倒向 5L 的桶中

对于顶点的表示，我们可以使用 10X + Y 这种方式。

代码链接🔗

我们的代码执行结果如下：

  1. [0, 50, 23, 20, 2, 52, 43]

这个结果表示的含义：

  • [0,0]
  • [5,0] 代表将 5L 的桶装满水
  • [2,3] 代表将 5L 的桶里面的水倒向 3L的桶中，将 3L 桶装满
  • [2,0] 代表将 3L 的桶里面的水倒空
  • [0,2] 代表将 5L 桶里面的 2L 水全部倒向 3L 的桶中
  • [5,2] 代表将 5L 的桶装满水
  • [4,3] 代表将 5L 的桶里面的水倒向 3L 的桶中，将 3L 的桶装满后，5L 的桶中还剩余 4L 的水，整个过程结束

其实这个题目和 LeetCode 上的一个问题 365. 水壶问题 相类似，如果感兴趣的同学可以自己尝试做一下，在我的代码仓中，也有这道问题的题解。

五：River Crossing Puzzle

River Crossing Puzzle
image.png
River Crossing Puzzle 也是一道非常著名的，可以使用图论算法解决的智力题。

题目如下：

农夫需要把狼，羊，菜和自己运输到河到对岸去。只有农夫可以划船，并且船只能承载农夫和另外一样东西。还有一个棘手的问题是，如果没有农夫看着，羊会偷吃菜，狼会吃羊。请考虑一种方法，让农夫可以安全地安排这些东西和他自己过河。

有了上一道题目的经验，我们可以轻松地将这个问题转换为图模型。

我们定义一个长度为 4 的字符串来表示对岸的状态其中，0 位表示农夫，1 位置表示狼，2 位置表示羊，3 位置表示菜。

我们知道，狼和羊无法单独在一起，羊和菜无法单独在一起，我们可以像转盘锁这个问题一样定义一个数组 deadends，该数组表示会出现狼吃羊或羊吃菜的所有情况，deadends 数组如下：

  1. {"0111","0110","0011","1000","1001","1100"}

我们求解的就是从初始状态 “0000” 到结束状态 “1111” 的过程。

代码链接🔗

代码请点击链接进行查看，运行测试程序，测试程序输出结果如下：

  1. [0000, 1010, 0010, 1110, 0100, 1101, 0101, 1111]

这个结果表示的含义为：

  1. 初始状态，农夫，狼，羊，菜都在河岸的左侧
  2. 农夫带着羊过河
  3. 农夫自己回来
  4. 农夫带着狼过河
  5. 农夫带着羊回来
  6. 农夫带着菜过河
  7. 农夫自己回来
  8. 农夫带着羊过河，所有物品和农夫到达对岸

六：滑动谜题

773. 滑动谜题

我们这一次来看一个 LeetCode 上困难级别的问题：滑动谜题。

题目给定的二维数组 board 是谜板的初始状态，最终要到达的状态为：[[1,2,3],[4,5,0]]。
从初始状态到达一个最终状态，这一类问题我们很自然地想到图论。该问题的本质属于无权图的最短路径求解。

image.png
题目其实并不难，代码复杂的部分在如何将谜板这个二维数组的信息表示为一种状态。
该状态可以是 Integer 类型的数字或 String 字符串。

譬如，谜板的二维数组信息是：[[1,2,3],[4,0,5]]，我们可以将对应的状态表示为 123405 这个数字；或者，我们也可以将该状态表示为 “123405” 这个字符串。

无论是哪种转换方法，都应该保证谜板二维数组的信息和状态保证一致性，正确性。

本题我使用了 Integer 数字来表示谜板的状态，有兴趣的朋友可以尝试一下使用字符串来表示状态信息。

代码如下：

  1. class Solution {
  2.     private boolean[] visited;
  3.     private int[] pre;
  4.     private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
  6.     public int slidingPuzzle(int[][] board) {
  7.         visited = new boolean[550000];
  8.         pre = new int[550000];
  10.         Queue<Integer> q = new LinkedList<>();
  11.         int initState = board2num(board);
  12.         if (initState == 123450) return 0;
  14.         q.offer(initState);
  15.         visited[initState] = true;
  16.         pre[initState] = 0;
  18.         while (!q.isEmpty()) {
  19.             int cur = q.poll();
  20.             List<Integer> nexts = getNexts(cur);
  21.             for (int next : nexts) {
  22.                 if (!visited[next]) {
  23.                     q.offer(next);
  24.                     visited[next] = true;
  25.                     pre[next] = pre[cur] + 1;
  26.                     if (next == 123450)
  27.                         return pre[next];
  28.                 }
  29.             }
  30.         }
  31.         return -1;
  32.     }
  34.     private List<Integer> getNexts(int cur) {
  35.         List<Integer> res = new ArrayList<>();
  36.         int[][] board = num2board(cur);
  37.         int zeroX = -1;
  38.         int zeroY = -1;
  39.         for (int i = 0; i < 2; i++)
  40.             for (int j = 0; j < 3; j++)
  41.                 if (board[i][j] == 0) {
  42.                     zeroX = i;
  43.                     zeroY = j;
  44.                 }
  46.         for (int d = 0; d < 4; d++) {
  47.             int nextX = zeroX + dirs[d][0];
  48.             int nextY = zeroY + dirs[d][1];
  49.             if (isValid(nextX, nextY)) {
  50.                 swap(board, zeroX, zeroY, nextX, nextY);
  51.                 res.add(board2num(board));
  52.                 swap(board, zeroX, zeroY, nextX, nextY);
  53.             }
  54.         }
  55.         return res;
  56.     }
  58.     private boolean isValid(int x, int y) {
  59.         return x >= 0 && x < 2 && y >= 0 && y < 3;
  60.     }
  62.     private void swap(int[][] board, int x1, int y1, int x2, int y2) {
  63.         int tmp = board[x1][y1];
  64.         board[x1][y1] = board[x2][y2];
  65.         board[x2][y2] = tmp;
  66.     }
  68.     private int[][] num2board(int num) {
  69.         int[][] res = new int[2][3];
  70.         for (int i = 0; i < 2; i++)
  71.             for (int j = 0; j < 3; j++)
  72.                 if (i == 0) {
  73.                     res[i][j] = getDigit(num, i * 2 + j);
  74.                 } else {
  75.                     res[i][j] = getDigit(num, i * 2 + j + 1);
  76.                 }
  78.         return res;
  79.     }
  81.     private int getDigit(int num, int index) {
  82.         String s = String.valueOf(num);
  84.         if (num > 100000) {
  85.             return s.charAt(index) - '0';
  86.         } else {
  87.             if (index == 0)
  88.                 return 0;
  89.             return s.charAt(index - 1) - '0';
  90.         }
  91.     }
  93.     private int board2num(int[][] board) {
  94.         return board[0][0] * 100000
  95.                 + board[0][1] * 10000
  96.                 + board[0][2] * 1000
  97.                 + board[1][0] * 100
  98.                 + board[1][1] * 10
  99.                 + board[1][2] * 1;
  100.     }
  101. }

那么该问题的时间复杂度是多少呢？

我们知道无论是 BFS/DFS 这两种算法的时间复杂度均为 O(V + E)，对于滑动谜题这个问题来说，每一个状态相当于一个顶点，一个顶点最多有上下左右四条边，所以 O(V + E) = O(V + 4V) = O(V)。

那么一共有多少种状态呢？题目给定了 2 * 3 个格子，对应了 6！个状态，所以，该算法的时间复杂度为 O(n!)。

七：图论搜索和人工智能

通过这一章的学习，我们知道 BFS 可以求解无向图的最短路径问题，这实际上就是一种最简单的基于搜索的人工智能。

这里给出一本书籍的链接：《Artificial Intelligence A Modern Approach》，感兴趣的朋友可以阅读。