【面试刷题】宽度优先搜索
一、最简洁的BFS算法的通用模板
1、适用于树和图的BFS模板
- 队列建议使用new ArrayDeque不建议使用new LinkedList（链表比数组慢）
//双端队列
Queue<Node> queue = new ArrayDeque<>();
HashMap<Node,Integer> distance = new HashMap<>();
//step 1 初始化
//把初始节点放到deque里面，如果有多个就都放进去
//并标记初始节点的距离为0，记录在distance的hashmap里
//distance有两个作用，一个是判断是否已经访问过，二是记录离起点的距离
queue.offer(node);
distance.put(node,0);
//step 2:不断访问队列
//while循环 + 每次pop队列中的一个点出来
while (!queue.isEmpty()) {
Node node = queue.poll();
//step 3:扩展相邻节点
//pop出的结点的相邻节点，加入队列并在distance中存储举例
for (Node neighbor : node.getNeighbors()) {
continue;
}
distance.put(neighbor, distance.get(node) + 1);
queue.offer(neighbor);
}
- 复杂度：图上BFS时间复杂度 = O(N + M)
2、LeetCode-133.克隆图
class Solution {
public Node cloneGraph(Node node) {
//特殊情况处理
if (node == null) {
return null;
}
//第一步：找到所有点
List<Node> nodes = findNodesByBFS(node);
//第二步：复制所有点
Map<Node, Node> mapping = copyNodes(nodes);
//第三部：复制所有边
copyEdges(nodes, mapping);
//返回与给定节点具有相同val的那个节点
return mapping.get(node);
}
//第一步：BFS找到所有点
private List<Node> findNodesByBFS(Node node) {
Queue<Node> queue = new LinkedList<>();
//用于保存所有的点，不重复，不漏掉
Set<Node> visited = new HashSet<>();
queue.offer(node);
//一旦入队，就要马上标记
visited.add(node);
while(!queue.isEmpty()) {
Node curNode = queue.poll();
for (Node neighbor : curNode.neighbors) {
//如果之前已经找到了这个点，无需再次BFS，否则死循环
if (visited.contains(neighbor)) {
continue;
}
//一旦访问，就要马上标记。
visited.add(neighbor);
queue.offer(neighbor);;
}
}
return new LinkedList<>(visited);
}
//第二步：复制所有点
private Map<Node,Node> copyNodes(List<Node> nodes) {
//(旧点 -> 新点)的映射
Map<Node,Node> mapping = new HashMap<>();
for (Node node : nodes) {
mapping.put(node, new Node(node.val));
}
return mapping;
}
//第三步：复制所有边
private void copyEdges(List<Node> nodes, Map<Node,Node> mapping) {
for (Node node : nodes) {
Node newNode = mapping.get(node);
//旧点有哪些邻居，新点就有哪些邻居
for (Node neighbor : node.neighbors) {
Node newNeighbor = mapping.get(neighbor);
newNode.neighbors.add(newNeighbor);
}
}
}
}
- 可以看出上面的代码，最主要的就是通过BFS找到所有的点。
3、LeetCode-127.单词接龙
①生成变换列表
②变换列表图示
③代码实现
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
//假设wordList不为空
//假设beginWord和endWord是非空的，且二者不同
//必须加入endWord。可以加入beginword
wordList.add(endWord);
HashSet<String> visited = new HashSet<String>();
Queue<String> queue = new LinkedList<String>();
queue.offer(beginWord);
visited.add(beginWord);
//记录最短路线长度，起始长度为1
int length = 1;
while(!queue.isEmpty()) {
//到下一层（不是当前层）的长度，相当于树的深度
length++;
//当前层有size个元素
int size = queue.size();
for (int i = 0; i < size; i++) {
String word = queue.poll();
//得到下一步的单词
for (String nextWord : getNextWords(word,wordList)) {
if (visited.contains(nextWord)) {
continue;
}
//如果下一层的词为尾词，直接返回当前到下一层（不是当前层）的长度
if (nextWord.equals(endWord)) {
return length;
}
//加入下一层，为后面BFS做准备
visited.add(nextWord);
queue.offer(nextWord);
}
}
}
//不能实现首尾接龙
return 0;
}
//找到可以和word接龙的所有单词
//比如word = 'hot'，dict = {'hot', 'hit', 'hog'},return ['hit','hog']
private ArrayList<String> getNextWords(String word, List<String> wordList) {
ArrayList<String> nextWords = new ArrayList<String>();
//枚举字典中的每个单词
for (String nextWord : wordList) {
boolean hashOneDiff = false;
for (int i = 0; i < word.length(); i++) {
//判断两个词是否只相差一个字母。如果是，则可以接龙
if (nextWord.charAt(i) != word.charAt(i)) {
//如果已经有一个不同了，那么直接就排除
if (hashOneDiff) {
hashOneDiff = false;
break;
}
hashOneDiff = true;
}
}
if (hashOneDiff) {
nextWords.add(nextWord);
}
}
return nextWords;
}
//新字符串
private String replace(String word, int index, char c) {
char[] chars = word.toCharArray();
chars[index] = c;
return new String(chars);
}
}
二、矩阵中的宽度优先搜索
1、LeetCode-200.岛屿数量
思路解析
代码实现
//定义一个class，表示坐标系中的一个点
class Coordinate {
int x, y;
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
}
class Solution {
//四个方向的偏移量
int[] deltaX = {0, 1, -1, 0};
int[] deltaY = {1, 0, 0, -1};
public int numIslands(char[][] grid) {
//特殊情况处理
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
return 0;
}
int islands = 0;
int row = grid.length, col = grid[0].length;
//记录某点是否被BFS过，如果之前已经被BFS过，不应该再次被BFS
boolean[][] visited = new boolean[row][col];
//遍历矩阵中的每一个点
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
//如果为海洋，无需BFS
//如果该点已经被visited，无需做冗余遍历，重复读取
if (grid[i][j]!='0' && !visited[i][j]) {
bfs(grid, i, j, visited);
islands++;
}
}
}
return islands;
}
//从一块土地出发，通过BFS，遍历整个岛屿
private void bfs(char[][] grid, int x, int y, boolean[][] visited) {
Queue<Coordinate> queue = new ArrayDeque<>();
queue.offer(new Coordinate(x, y));
visited[x][y] = true;
while (!queue.isEmpty()) {
Coordinate coor = queue.poll();
//遍历上下左右四个方向
for (int direction = 0; direction < 4; direction++) {
int newX = coor.x + deltaX[direction];
int newY = coor.y + deltaY[direction];
//如果不是有效的点，就继续
if (!isValid(grid, newX, newY, visited)) {
continue;
}
queue.offer(new Coordinate(newX, newY));
//一旦入队，标记此店已经参加过BFS
visited[newX][newY] = true;
}
}
}
//判断一个点是否可以被BFS
private boolean isValid(char[][] grid, int x, int y, boolean[][] visited) {
int n = grid.length, m = grid[0].length;
//如果出界，返回false
if (x < 0 || x>=n || y < 0 || y >= m) {
return false;
}
//如果已经BFS过，不要再次BFS，避免：1.死循环 2.冗余的BFS变量
if (visited[x][y]) {
return false;
}
//如果是'1' ，则为true；如果是0，则为false
return grid[x][y] == '1' ? true : false;
}
}
反思记录
- 处理矩阵的问题，上下左右坐标移动的模拟，通过偏移量。
- BFS的使用，去遍历周围的岛屿。
- 细节的处理，坐标系中的点的表示，visited数组传递的方法（避免使用全局变量），边界值的检测判断。
- 在实现BFS时候的队列，使用了ArrayDeque这个类。
2、LintCode-611.骑士的最短路线
- [题目链接](611 · 骑士的最短路线 - LintCode)
- 一维坐标具有唯一确定性
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
//8个方向的偏移量，这是骑士可以移动的
public static final int[] X_OFFSET = {1, 1, -1, -1, 2, 2, -2, -2};
public static final int[] Y_OFFSET = {2, -2, 2, -2, 1, -1, 1, -1};
public int shortestPath(boolean[][] grid, Point source, Point destination) {
//异常处理
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
return -1;
}
Queue<Point> queue = new ArrayDeque<>();
//记录从起点到(x,y)的最短距离，(x, y) 代表 到起点start的最短距离
Map<Integer,Integer> cellToDisMap = new HashMap();
int col = grid[0].length;
queue.offer(source);
//加上乘以col避免重复，把二维坐标换成一维坐标
cellToDisMap.put(source.x * col + source.y, 0);
while (!queue.isEmpty()) {
Point point = queue.poll();
int curPointKey = point.x * col + point.y;
if (point.x == destination.x && point.y == destination.y) {
return cellToDisMap.get(curPointKey);
}
//遍历8个不同的方向
for (int i = 0; i < 8; i++) {
int adjX = point.x + X_OFFSET[i];
int adjY = point.y + Y_OFFSET[i];
if (!isValid(adjX, adjY, grid)) {
continue;
}
//小套路：把二维坐标转换为一维坐标
int newPointKey = adjX * col + adjY;
//如果之前已经到达过此点，不可能再次BFS此点找到最短路径，还会造成死循环
if (cellToDisMap.containsKey(newPointKey)) {
continue;
}
queue.offer(new Point(adjX, adjY));
cellToDisMap.put(newPointKey, cellToDisMap.get(curPointKey) + 1);
}
}
return -1;
}
private boolean isValid(int x, int y, boolean[][] grid) {
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) {
return false;
}
//值1表示障碍物，返回false
return !grid[x][y];
}
}
三、拓扑排序Topological Sorting
1、什么是拓扑排序
在一个有向图中，对所有的节点进行排序，要求没有一个节点指向它前面的节点。
先统计所有节点的入度，对于入度为0的节点就可以分离，然后把这个节点指向的节点的入度减一。
一直重复上述操作，直到所有的节点都被分离出来。
如果最后不存在入度为0的节点，那就说明有环，不存在拓扑排序，也就是出现无解的情况。
细节描述：
- 统计每个点的入度
- 将每个入度为0的点，放入队列中，作为起始节点。
- 不断从队列中拿出一个点，去掉这个点的所有连边（指向其他点的边），其他点的相应入度-1
- 一旦发现新的入度为0的点，丢回队列当中。
2、LeetCode-207.课程表
[题目链接](207. 课程表 - 力扣（LeetCode） (leetcode-cn.com))
解题思路：
图 + 有依赖关系 + 有向 + （环） = 拓扑排序
- 统计每个点的入度
- 将每个入度为0的点放入队列中作为起始节点
- 不断从队列中拿出一个点，去掉这个点的所有连边（指向其他点的边），其他点的相应入度-1
- 一旦发现新的入度为0的点，丢回队列当中。
代码实现：
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
//构建图，代表（先修课 -> 多个后修课）的映射
List[] graph = new ArrayList[numCourses];
//图的初始化，每个先修课->空后修课List
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList<Integer>();
}
//1.统计每个点的入度，并构建图
int[] inDegree = new int[numCourses];
for (int[] edge : prerequisites) {
//比如[0,1]: 要上课程0，先学课程1，则0的入度加1。
//即有向图的箭头表示的是依赖关系，先修课程1，才能修课程0
//注意这里是，先修课->后修课程的映射，即入度还是后修的课程
graph[edge[1]].add(edge[0]);
inDegree[edge[0]]++;
}
Queue queue = new LinkedList();
//2.将每个入度为0的点放入队列中作为起始节点
for (int i = 0; i < inDegree.length; i++) {
if (inDegree[i] == 0) {
queue.add(i);
}
}
//记录已修课程的数量
int numChoose = 0;
//记录拓扑顺序
int[] topoOrder = new int[numCourses];
//3.不断从队列中拿出一个点，去掉这个点的所有连边（指向其他点的边），其他点的相应的入度-1
while (!queue.isEmpty()) {
int nowPos = (int) queue.poll();
//记录已修课程
topoOrder[numChoose] = nowPos;
numChoose++;
//从这个课程指向的其他课程，遍历，入度减一
for (int i = 0; i < graph[nowPos].size(); i++) {
int nextPos = (int) graph[nowPos].get(i);
//当前点的邻居入度减一，表示每个后修课程的一门先修课程已经完成
inDegree[nextPos]--;
//4.一旦发现新的入度为0的点，丢回队列当中
//表示一门后修课程的所有先修课程已经完成，可以被修了
if (inDegree[nextPos] == 0) {
queue.add(nextPos);
}
}
}
//如果需要拓扑排序，也可以在此返回topoOrder
return (numChoose == numCourses) ? true : false;
}
}
值得学习的点：
- 在定义先修课程和后修课程时，通过一个List来表示，先修的课程放到最前面，后修的课程放到后面。
- 在这个图的定义中，List[] graph，很巧妙，通过课程的下标和数组下标结合在了一起。
四、BFS小结
- 能够用BFS的不要用DFS
- BFS使用的场景
- 连通块问题
- 层级遍历问题
- 拓扑排序问题
- 是否需要层级遍历
- 需要多一重循环，queue.size()
- 矩阵坐标变换数组