算法.图论-BFS及其拓展

广度优先搜索简介

1. bfs的特点是逐层扩散, 从源头到目标点扩散了几层, 最短路就是多少

2. bfs的使用特征是任意两个节点的距离(权值)是相同的(无向图, 矩阵天然满足这一特点)

3. bfs开始的时候可以是单个源头, 也可以多个源头(单源bfs, 和多源bfs)

4. bfs进出队列的时候可以是单点弹出, 也可以是整层弹出

   如果是单点弹出的时候, 队列中存放的是当前的节点和距离源点的距离

   整层弹出则不需要, 只需要保留一个level计数就可以知道到源点的距离

5. bfs进行时通常需要一个visit数组(一般是boolean[][])来标记已经遍历到的位置

6. bfs的时候一个点向四个方向遍历的时候通常可以用一个move数组搞定(下面是举例)

   //建立一个全局的move数组来进行四个方向的遍历(上, 右, 下, 左)
   private static final int[] move = new int[]{-1, 0, 1, 0, -1};
   //假设下面的函数是用来进行 (i, j) 的遍历的
   private static void traversal(int i, int j, int[][] matrix, boolean[][] visit){//不用写四个if, 仅仅需要进行for循环四次就可以了int r = matrix.length;int c = matrix[0].length;for(int k = 0; k < 4; k++){int ni = i + move[k];int nj = j + move[k + 1];if(ni >= 0 && ni < r && nj >= 0 && nj < c && !visit[ni][nj]){//下一个位置不越界并且没有访问过//.....进行处理逻辑, 并最终把visit数组的这一个位置置为truevisit[ni][nj] = true;}}
   }
   

7. bfs设计的时候有很多的剪枝的操作需要进行一定的摸索

经典bfs习题

地图分析

链接: leetcode1162.地图分析

题目简介:

解释一下什么是曼哈顿距离, 就是一个点到另外一个点的横坐标的差值和纵坐标的差值之和, 这与我们习惯认为的对角线距离区别开

这种距离的定义通常用于矩形的表格之中(实质上: bfs最广的应用就是矩形格之中, 因为这是一种天然的无向图)

这道题本质上是要找距离陆地最近的海洋的最远的距离, 翻译成人话就是寻找距离陆地最远的海洋, 那我们直接以陆地为源点开始进行bfs即可

我们下面给出来两种实现的方案

第一种是单点弹出的方法

    //创建一个move数组private static final int[] move = new int[]{-1, 0, 1, 0, -1};//创建一个全局的visit数组private static final int MAXM = 101;private static final boolean[][] visit = new boolean[MAXM][MAXM];//方法一: 单点弹出的方式public int maxDistance(int[][] grid) {int r = grid.length;int c = grid[0].length;int seas = 0;Queue<int[]> q = new ArrayDeque<>();//遍历一下grid数组初始化队列元素同时初始化visit数组for(int i = 0; i < r; i++){for(int j = 0; j < c; j++){if(grid[i][j] == 1){visit[i][j] = true;q.offer(new int[]{i, j, 0});}else{visit[i][j] = false;seas++;}}}//特殊条件直接返回if(seas == r * c || seas == 0){return -1;}//进行bfs的主流程int distanse = 1;while(!q.isEmpty()){int[] cur = q.poll();//向四个方向尝试扩展for(int k = 0; k < 4; k++){int nx = cur[0] + move[k];int ny = cur[1] + move[k + 1];if(nx >= 0 && nx < r && ny >= 0 && ny < c && !visit[nx][ny]){visit[nx][ny] = true;q.offer(new int[]{nx, ny, cur[2] + 1});distanse = Math.max(distanse, cur[2] + 1);}}}return distanse;}
}

第二种就是整层弹出的方法

class Solution {//创建一个move数组private static final int[] move = new int[]{-1, 0, 1, 0, -1};//创建一个全局的visit数组private static final int MAXM = 101;private static final boolean[][] visit = new boolean[MAXM][MAXM];//方法二 : 整层弹出的方式public int maxDistance(int[][] grid) {int r = grid.length;int c = grid[0].length;int seas = 0;Queue<int[]> q = new ArrayDeque<>();//遍历一下grid数组初始化队列元素同时初始化visit数组for(int i = 0; i < r; i++){for(int j = 0; j < c; j++){if(grid[i][j] == 1){visit[i][j] = true;q.offer(new int[]{i, j});}else{visit[i][j] = false;seas++;}}}//特殊条件直接返回if(seas == r * c || seas == 0){return -1;}//进行bfs的主流程int level = 0;while(!q.isEmpty()){level++;int sz = q.size();while(sz-- != 0){int[] cur = q.poll();//尝试向四个方向扩展for(int k = 0; k < 4; k++){int nx = cur[0] + move[k];int ny = cur[1] + move[k + 1];if(nx >= 0 && nx < r && ny >= 0 && ny < c && !visit[nx][ny]){q.offer(new int[]{nx, ny});visit[nx][ny] = true;}}}}return level - 1;}
}

贴纸拼词

链接: [leetcode691.贴纸拼词](. - 力扣（LeetCode）)

题目描述:

这个题的解题思路就是, 对于目标字符串target, 我们想要使用最少的代价进行拼词,

这道题如何想到用bfs主要就是对于一个字符串

target, 我们提供的每一个词都有对应的一种展开, 如下图

图片:

从上面的演示过程也不难看出, 我们这个本题剪枝的关键就是对target的进行排序操作, 主要就是优先削减头部的字符

代码实现如下(重点在理解逻辑)

class Solution {public static int minStickers(String[] stickers, String target) {//首先对数组中的单词排序并进行词频统计List<int[]> times = new ArrayList<>();for(int i = 0; i < stickers.length; i++){int[] temp = new int[26];String changeStr = sort(stickers[i], temp);stickers[i] = changeStr;times.add(temp);}//排序一下target字符串int[] targetTime = new int[26];target = sort(target, targetTime);Queue<String> q = new ArrayDeque<>();HashSet<String> set = new HashSet<>();StringBuilder sp = new StringBuilder();//进行bfs的主流程q.offer(target);int level = 0;//本质上还是我们弹出的逻辑没有搞懂, 我们应该一层一层的弹出while(!q.isEmpty()){int sz = q.size();level++;while(sz-- != 0){int[] curTime = new int[26];String cur = q.poll();//统计一下当前的词频for(int i = 0; i < cur.length(); i++){curTime[cur.charAt(i) - 'a']++;}for(int i = 0; i < stickers.length; i++){if(times.get(i)[cur.charAt(0) - 'a'] != 0){String next = buildStr(curTime, times.get(i), sp);if(next.equals("")) return level;if(!set.contains(next)) {set.add(next);q.offer(next);}}}}}return -1;}//对字符串排序的方法, 顺便统计一下词频private static String sort(String s, int[] temp){char[] cs = s.toCharArray();for(char elem : cs){temp[elem - 'a']++;}Arrays.sort(cs);return String.valueOf(cs);}//生成一个新的字符串private static String buildStr(int[] curTime, int[] time, StringBuilder sp){sp.setLength(0);for(int i = 0; i < 26; i++){if(curTime[i] != 0){for(int j = 0; j < Math.max(curTime[i] - time[i], 0); j++){sp.append((char)(i + 'a'));}}}return sp.toString();}}

01bfs解析

基本过程

01bfs是一种特殊的bfs, 适用于01图找寻最短路径的情况, 01bfs时间复杂度是O(节点数量 + 边的数量) 下图是我们的实例

图片:

上面就是一个01bfs找寻最短路径的情况, 我们的解题的流程是固定的, 如下(正确性证明略), 主要就是双端队列结合bfs

1. 创建一个distance表, 含义就是源点到i点的最短距离是多少

   大小就是所有的节点位置, 初始化所有点的distance[i] = Integer.MAX_VALUE

2. 将源点加入双端队列, 并修改distance[源点] = 0

3. 当队列不为空的时候进入循环(下面就是伪代码)

   while(!queue.isEmpty()){//弹出一个节点(弹出的时候一定从头部弹出)Node node = queue.poll();//如果这个位置就是要找的目标节点就直接返回if(node == targetNode) return distance[node];//找到这个节点去的下一个位置(可能有多个...)int next = node -> next;//weight就是这两个点之间的权值(0 or 1)int weight = 0 or 1;    if(distance[node] + weight < distance[next]){//此时说明到达next的位置可以边的更小就更新distance[next] = distance[node] + weight;//然后在队列中加入这个位置, 如果刚才的权值weight == 0, 就从头部加入, 如果是1就从尾部加入if(weight == 0){queue.offerFirst(node);}else{queue.offerLast(node);}}
   }
   

相关习题

图片:

链接: leetcode2290.到达角落的最小代价

其实就是01bfs的模板题

class Solution {//经典01dfs板子题private static final int[] move = new int[]{-1, 0, 1, 0, -1};public int minimumObstacles(int[][] grid) {int r = grid.length;int c = grid[0].length;//初始化一个distance数组int[][] distance = new int[r][c];for(int i = 0; i < r; i++){for(int j = 0; j < c; j++){distance[i][j] = Integer.MAX_VALUE;}}//创建一个双端队列Deque<int[]> dq = new ArrayDeque<>();dq.offer(new int[]{0, 0});distance[0][0] = 0;while(!dq.isEmpty()){int[] cur = dq.poll();//如果是目标节点if(cur[0] == r - 1 && cur[1] == c - 1) return distance[cur[0]][cur[1]];//尝试向四个方向扩展for(int k = 0; k < 4; k++){int nx = cur[0] + move[k];int ny = cur[1] + move[k + 1];if(nx >= 0 && nx < r && ny >= 0 && ny < c && distance[cur[0]][cur[1]] + grid[nx][ny] < distance[nx][ny]){distance[nx][ny] = distance[cur[0]][cur[1]] + grid[nx][ny];if(grid[nx][ny] == 0){dq.offerFirst(new int[]{nx, ny});}else{dq.offerLast(new int[]{nx, ny});}}}}return -1;}
rst(new int[]{nx, ny});}else{dq.offerLast(new int[]{nx, ny});}}}}return -1;}
}

链接: leetcode1368.箭头数组的最短代价

图片:

class Solution {//这个move数组的设计是比较的精巧的private static final int[][] move = {{0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};public int minCost(int[][] grid) {int r = grid.length;int c = grid[0].length;//初始化distance数组int[][] distance = new int[r][c];for(int i = 0; i < r; i++){Arrays.fill(distance[i], Integer.MAX_VALUE);}//创建双端队列Deque<int[]> dq = new ArrayDeque<>();dq.offer(new int[]{0, 0});distance[0][0] = 0;while(!dq.isEmpty()){int[] cur = dq.poll();int x = cur[0];int y = cur[1];if(x == r - 1 && y == c - 1) return distance[x][y];for(int i = 1; i < 5; i++){int nx = x + move[i][0];int ny = y + move[i][1];int weight = i == grid[x][y] ? 0 : 1;if(nx >= 0 && nx < r && ny >= 0 && ny < c && distance[x][y] + weight < distance[nx][ny]){distance[nx][ny] = distance[x][y] + weight;if(weight == 0){dq.offerFirst(new int[]{nx, ny});}else{dq.offerLast(new int[]{nx, ny});}}}}return -1;}
}