Awesome算法解题框架——广度优先搜索（BFS）
2020-03-22 本文已影响0人
m2fox
Awesome算法解题框架系列：致力于探讨算法问题的框架思维，形成解题框架，用一个框架以点带面解决一类问题。问题千变万化，算法思维框架是不变的，以不变应万变。
广度优先搜索（以下简称BFS）是图的搜索算法中的一种基础算法，其核心思想是从源点出发一圈一圈向外扩展、逐层地毯式推进搜索。使用的核心数据结构是队列，此外为了存储路径，还需要一个哈希表。
下面是两个使用BFS算法的模板题，本文将从这两个问题出发，总结出BFS算法的通用解题框架模板，力求使用这套模板，可以快速解决BFS问题。
- leetcode-cn-695 岛屿的最大面积：https://leetcode-cn.com/problems/max-area-of-island/
- POJ-3984 迷宫问题：http://poj.org/problem?id=3984
岛屿的最大面积
问题分析
图中上下左右连在一起的1的区域就是陆地，要找到这些陆地区域中最大的面积，朴素的思路就是：先找到所有的陆地区域，然后计算出最大的那个区域的面积。那么核心问题就转换为如何找到图中所有的陆地区域？当然是用BFS了。
和其他的BFS寻找最短路径问题稍有不同的是，本题并不需要寻找一个最短路径，因此不需要存储路径有关的信息。
代码实现
用Java实现：
// AC@7ms 12% 89%
class Solution {
public int maxAreaOfIsland(int[][] grid) {
// - 判空
if (null == grid || null == grid[0]) {
return 0;
}
// - 陆地是否处理过的标记数组
int row = grid.length;
int column = grid[0].length;
boolean[][] marked = new boolean[row][column];
// - 从左到右、从上到下第一个未被处理的陆地开始BFS处理
int maxLandArea = 0;
Queue<int[]> queue = new LinkedList<>();
for(int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if (grid[i][j] == 1 && !marked[i][j]) {
// 当前陆地面积
int curArea = 0;
queue.add(new int[]{i, j});
while (!queue.isEmpty()) {
// 当前点
int[] cur = queue.poll();
curArea++;
// 标记当前点已处理
marked[cur[0]][cur[1]] = true;
// 获取当前点的上下左右未被处理的邻居陆地节点
List<int[]> neighbors = unmarkedLandNeighbors(grid, cur, marked);
if (null != neighbors && neighbors.size() > 0) {
for (int[] nei: neighbors) {
queue.offer(nei);
// 标记当前邻居点已处理，否则会被重复添加
marked[nei[0]][nei[1]] = true;
}
}
}
// 更新最大面积
if (curArea > maxLandArea) {
maxLandArea = curArea;
}
}
}
}
return maxLandArea;
}
// 获取一个点上下左右的未被处理的邻居陆地节点的坐标列表，(行，列）下标二元组
private List<int[]> unmarkedLandNeighbors(int[][] grid, int[] point, boolean[][] marked) {
int row = grid.length;
int column = grid[0].length;
int r = point[0];
int c = point[1];
List<int[]> neighbors = new ArrayList<>();
// 上
if (r > 0 && grid[r-1][c] == 1 && !marked[r-1][c]) {
neighbors.add(new int[]{r-1, c});
}
// 下
if (r < row - 1 && grid[r+1][c] == 1 && !marked[r+1][c]) {
neighbors.add(new int[]{r+1, c});
}
// 左
if (c > 0 && grid[r][c - 1] == 1 && !marked[r][c-1]) {
neighbors.add(new int[]{r, c-1});
}
// 右
if (c < column - 1 && grid[r][c+1] == 1 && !marked[r][c+1]) {
neighbors.add(new int[]{r, c+1});
}
return neighbors;
}
}
迷宫问题
问题分析
这是一个典型的BFS算法问题，迷宫中有通路，也有障碍，从起点开始，运用BFS的逐层地毯式搜索，过程中记录每个搜索过的点的上一个节点的哈希表，直到遇到终点，最终就可以根据这个哈希表、从后往前"按图索骥"找到从起点到终点的最短路径。
代码实现
用Java实现：
// poj-3984 迷宫问题
import java.util.*;
class Main {
private static Main main = new Main();
public static void main(String[] argv) {
Scanner sc = new Scanner(System.in);
int[][] maze = new int[5][5];
for(int i = 0; i < 5; i++){
for(int j = 0; j < 5; j++){
maze[i][j] = sc.nextInt();
}
}
main.printShortestPath(maze);
}
// 打印从左上角到右下角的最短路径
private static void printShortestPath(int[][] maze) {
// - 判空
if (null == maze || null == maze[0] || maze.length == 0 || maze[0].length == 0) {
return;
}
// - 找到最短路径前驱map
Map<List<Integer>, int[]> shortestPathPreMap = findShortestPathPreMap(maze);
// - 解析最短路径前驱map为最短路径列表
List<int[]> path = parsePath(shortestPathPreMap, new int[]{4,4});
// - 打印最短路径
for (int[] p: path) {
System.out.println("(" + p[0] + ", " + p[1] + ")");
}
}
// 找到从左上角到右下角的最短路径，返回路径前驱节点map
private static Map<List<Integer>, int[]> findShortestPathPreMap(int[][] maze) {
int row = maze.length;
int col = maze[0].length;
// - 标记某个点的前驱节点的哈希表
Map<List<Integer>, int[]> preMap = new HashMap<List<Integer>, int[]>();
// - 标记迷宫中的点有没有被搜索过的标记数组
boolean[][] searched = new boolean[row][col];
// - 待查找队列，存放待查找的点的（行，列）坐标，先把左上角的点入队
Queue<int[]> searchQueue = new LinkedList<int[]>();
searchQueue.offer(new int[]{0,0});
// - 遍历待查找队列
while (!searchQueue.isEmpty()) {
// - 出队当前点
int[] cur = searchQueue.poll();
// - 标记当前点为处理过
searched[cur[0]][cur[1]] = true;
// - 遍历当前点的邻居节点列表
List<int[]> neighbors = getNeighbors(maze, cur, searched);
if (neighbors.size() > 0) {
for (int[] nei: neighbors) {
// 记录前驱节点
preMap.put(arr2List(nei), cur);
// 如果是终点，则返回前驱关系哈希表
if (nei[0] == row-1 && nei[1] == col-1) {
return preMap;
}
// 如果不是终点，入队，并标记为已经搜索过
searchQueue.offer(nei);
searched[nei[0]][nei[1]] = true;
}
}
}
return null;
}
// 获取cur点当前上下左右未被查找过且不是障碍物的邻居节点列表
private static List<int[]> getNeighbors(int[][] maze, int[] cur, boolean[][] searched) {
List<int[]> neighbors = new ArrayList<int[]>();
int rowLen = maze.length;
int colLen = maze[0].length;
int row = cur[0];
int col = cur[1];
// 上
if (row > 0 && !searched[row-1][col] && maze[row-1][col] != 1) {
neighbors.add(new int[]{row-1, col});
}
// 下
if (row < rowLen - 1 && !searched[row+1][col] && maze[row+1][col] != 1) {
neighbors.add(new int[]{row+1, col});
}
// 左
if (col > 0 && !searched[row][col-1] && maze[row][col-1] != 1) {
neighbors.add(new int[]{row, col-1});
}
// 右
if (col < colLen - 1 && !searched[row][col+1] && maze[row][col+1] != 1) {
neighbors.add(new int[]{row, col+1});
}
return neighbors;
}
// 从preMap中解析出从起点到终点的路径列表
private static List<int[]> parsePath(Map<List<Integer>, int[]> preMap, int[] end) {
// 从起点到终点的路径列表
List<int[]> path = new ArrayList<int[]>();
// 当前节点：终点
int[] cur = end;
while (null != cur && !(cur[0] == 0 && cur[1] == 0)) {
path.add(cur);
cur = preMap.get(arr2List(cur));
}
// 加入起点
path.add(new int[]{0,0});
// 反转path
Collections.reverse(path);
return path;
}
// 把整型数组转为整型列表
private static List<Integer> arr2List(int[] arr) {
List<Integer> nums = new ArrayList<Integer>();
for (int n: arr) {
nums.add(n);
}
return nums;
}
}
BFS算法框架总结
核心框架
把起点加入待搜索队列
while 待搜索队列不为空:
出队当前元素，并标记为已处理
获取当前元素的可达、合法、未被标记的邻居列表
for neighbor in [邻居列表]:
把neighbor加入待搜索队列
标记neighbor为已处理
核心框架伪代码
根据上面两个题目的代码，可以抽象出BFS算法解体框架的伪代码，伪代码中采用模块化的思想，封装了3个核心函数，每一个函数力求只做一件（简单的）事情：
// BFS算法主函数
BFS(matrix, start, end):
pre_map <- GET-SHORTEST-PATH-PRE-MAP(matrix, start, end)
path <- PARSE-PRE-MAP(pre_map, start, end)
return path
// 找到从起点到终点的最短路径的前驱关系哈希表
GET-SHORTEST-PATH-PRE-MAP(matrix, start, end):
// 待搜寻队列
search_queue <- empty queue
// 已搜寻过的点
searched_map <- empty hash map, all default false
// <某个点: 前一个点>的关系表
pre_map <- empty hash map
// 一开始将起点放入待搜寻队列
search_queue <- enqueue start
while search_queue is not empty:
cur <- dequeue from search_queue
// 标记当前点为已搜索过
searched_map[cur] <- true
neighbors <- GET-NEIGHBORS(cur)
for nei in neighbors:
// 记录前驱点关系
pre_map[nei] <- cur
// 判断是否找到终点
if nei is end:
return pre_map
search_queue <- enqueue nei
searched_map[nei] <- true
// 找到一个点的可达、且未被标记过的邻居点列表
GET-NEIGHBORS(matrix, cur, searched_map):
neighbors <- empty list
for point in up, down, left, right:
if point can access and searched_map[point] is false:
neighbors <- add point
return neighbors
// 把前驱关系哈希表解析为一个从起点到终点的路径列表
PARSE-PRE-MAP(pre_map, start, end):
path <- empty list
cur <- end
while cur is not start:
path <- add cur
cur <- pre_map[cur]
path <- add start
path <- reverse path
return path
Java实现时的几点注意事项
使用Java实现上述框架的时候，需要注意如下几点事项：
- Java中的队列可以使用
LinkedList，其实现了Queue接口，其入队方法为offer，出队方法为poll，判断是否为空的方法为isEmpty。 - 为了方便，可以优先使用
int[2]数组来表示一个点在矩阵中的(行, 列)坐标。 - 不能用数组作为Map的key，因为数组没有实现hashCode方法，而用整型List是可以作为Map的key的，有完全相同元素的两个List，其hachCode也是相同的。
- 寻找一个点的可达、未搜寻过的邻居节点的时候，可以按照
上下左右的顺序进行查找，防止思路混乱。
总结
BFS算法的框架是非常明晰的，没有多少弯弯绕的东西，本文中用伪代码给出的解题框架适用于用二维矩阵表示的图，如果是以其他形式表示的图，那么代码只需稍作修改，也可以同样适用，框架思想是相通的。
