强化面试中常用的算法 -深度与广度优先遍历
目录
1 回顾
2 深度优先遍历和广度优先遍历
2.1 深度优先搜索算法
2.2 广度优先搜索算法
3. 总结
1 回顾
在上一篇文章中，总结了一些关于递归和回溯的相关知识点。
今天给大家总结一下深度优先遍历(DFS)和广度优先遍历(BFS)
2 深度与广度优先搜索算法
深度优先搜索算法(DFS)和广度优先搜索算法(BFS)，这两种算法经常在算法面试题中出现，它在整个算法知识点中占⽐⾮常⼤；应⽤最多的地⽅是对图进⾏遍历（树也是图的⼀种）。
2.1 深度优先搜索算法
DFS 解决什么问题
DFS解决的是连通性的问题，即给定两⼀个起始点（或某种起始状态）和⼀个终点（或某种最终状态），判断是否有⼀条路径能从起点连接到终点。很多情况下，连通的路径有很多条，只需要找出⼀条即可，DFS 只关⼼路径存在与否，不在乎其⻓短。
算法的思想
从起点出发，选择⼀个可选⽅向不断向前，直到⽆法继续为⽌然后尝试另外⼀种⽅向，直到最后⾛到终点
看个例子
假设我们有这么⼀个图，⾥⾯有A, B, C, D, E, F, G, H 8个顶点，点和点之间的联系如下图所示：
如何对这个图进⾏深度优先的遍历呢？
- 深度优先遍历必须依赖栈（Stack）这个数据结构
- 栈的特点是后进先出（LIFO）
步骤：
第一步，选择一个初始起点，让我们从顶点A开始，将A压入栈，标记A为访问过，并把它放到结果中；
第二步，寻找与A相连，并且还没有被访问过的顶点，我们看到，顶点A与B，G，D相连，而且它们都还没有被访问过，我们按照字母顺序处理，所以将B压入栈，标记它为访问过，并输出到结果中；
第三步，现在我们在顶点B上，重复上面的操作，由于B与A,，E，F相连，如果按照字母顺序处理的话，A应该是要被访问的，但是A已经被访问了，所以我们访问顶点E，将E压入栈，标记它为访问过，并输出到结果中；
第四步，从E开始，E与B，G相连，但是B已经被访问过了，所以下一个被访问的是G，将G压入栈，标记它为访问过，并输出到结果中；
第五步，现在我们在顶点G的位置，由于与G相连的顶点都被访问过了，类似于走进了一个死胡同，必须尝试其他入口了，现在要做的就是简单的将G从栈里弹出，表示我们从G这里已经无法继续走下去了，看看能不能从前一个路口找到出路，可以看到，每次我们在考虑下一个要被访问的点是什么的时候，如果发现周围的顶点都被访问了，就把当前的节点弹出；
第六步，现在栈的顶部记录的是顶点E，我们来看看与E相连的节点中，有没有还没有被访问到的，我们发现它们都被访问了，所以把E也弹出；
第七步，当前栈的顶点是B，看看它周围还有没有还没有被访问到的，我们发现有F，于是把F压入栈，标记它为访问过，并输出到结果中；
第八步，当前节点是F，与F相连且还没有被访问过的点是C和D，按照字母顺序来，下一个被访问的点是C，将C压入栈，标记它为访问过，并输出到结果中；
第九步，当前节点是C，与C相连且还没有被访问过的点是H，将H压入栈，标记它为访问过，并输出到结果中；
第十步，当前节点是H，由于与它相连的节点都被访问过了，将它弹出；
第十一步，当前节点是C，由于与它相连的节点都被访问过了，将它弹出；
第十二步，当前节点是F，与F相连且还没有被访问过的点是D，将D压入栈，标记它为访问过，并输出到结果中；
第十三步，当前节点是D，由于与它相连的节点都被访问过了，将它弹出；以此类推，顶点F，B，A都被访问过了，将它们一一弹出栈就行，当栈中没有元素处理了，我们的整个遍历就结束。
例题分析
- 给定⼀个⼆维矩阵代表⼀个迷宫
- 迷宫⾥⾯有通道，也有墙壁，有墙壁的地⽅不能通过
- 通道由数字0表示，⽽墙壁由-1表示
- 现在问能不能从A点⾛到B点？
代码实现
boolean dfs(int maze[][], int x, int y) {
if(x == B[0] && y == B[1]) {
return true;
}
maze[x][y] = -1;
for (int d = 0; d < 4; d++) {
int i = x + dx[d], j = y + dy[d];
if(isSafe(maze, i, j) && dfs(maze, i, j)) {
return true;
}
}
return false;
}
步骤
1：判断是否抵达了⽬的地B，是则⽴即返回
2：标记当前点已经被访问过了
3：在规定的四个⽅向上进⾏尝试
4：如果有⼀条路径被找到了，则返回true
5：尝试了所有可能还没找到B，则返回false
DFS的递归实现
利⽤递归去实现DFS可以让代码看上去很简洁
递归的时候需要将当前程序中的变量以及状态压⼊到系统的栈⾥⾯
压⼊和弹出栈都需要较多的时间，如果需要压⼊很深的栈，会造成运⾏效率低下
DFS的⾮递归实现
栈的数据结构也⽀持压⼊和弹出操作
完全可以利⽤栈来提⾼运⾏效率
代码实现
boolean dfs(int maze[][], int x, int y) {
Stack<Integer[]> stack = new Stack<>();
stack.push(new Integer[] {x, y});
maze[x][y] = -1;
while (!stack.isEmpty()) {
Integer[] pos = stack.pop();
x = pos[0]; y = pos[1];
if (x == B[0] && y == B[1]) {
return true;
}
for (int d = 0; d < 4; d++) {
int i = x + dx[d], j = y + dy[d];
if (isSafe(maze, i, j)) {
stack.push(new Integer[] {i, j});
maze[i][j] = -1;
}
}
}
return false;
}
步骤
1：创建⼀个Stack，⽤来将要被访问的点压⼊以及弹出
2：将起始点压⼊Stack，并标记它被访问过
3：只要Stack不为空，就不断地循环，处理每个点
4：从堆栈取出当前要处理的点
5：判断是否抵达了⽬的地B，是则返回true
6：如果不是⽬的地，就从四个⽅向上尝试
7：将各个⽅向上的点压⼊堆栈，并把标记为访问过
8：尝试了所有可能还没找到B，则返回false
DFS复杂度分析
由于DFS是图论⾥的算法，分析利⽤DFS解题的复杂度时，应当借⽤图论的思想，图有两种表示⽅式：
‣ 邻接表（图⾥有V个顶点，E条边）
访问所有顶点的时间为O(V)，查找所有顶点的邻居的时间为O(E)，所以总的时间复杂度是O(V+E)
‣ 邻接矩阵（图⾥有V个顶点，E条边）
查找每个顶点的邻居需要O(V)的时间，所以查找整个矩阵的时候需要O(V2)的时间
利⽤DFS在迷宫⾥找⼀条路径
由于迷宫是⽤矩阵表示，所以假设它是⼀个M⾏N列邻接矩阵
‣ 时间复杂度为O(M × N)
因为⼀共有M × N个顶点，所以时间复杂度就是O(M × N)
‣ 空间复杂度为O(M × N)
DFS需要堆栈来辅助，在最坏情况下所有顶点都被压⼊堆栈，所以它的空间复杂度是O(V)，即O(M × N)
如何利⽤ DFS 寻找最短路径？
暴⼒解题法
找出所有路径，然后⽐较它们的⻓短，找出最短的那个
如果硬要使⽤DFS去找最短的路径，我们必须尝试所有的可能
DFS解决的只是连通性问题，不是⽤来求解最短路径问题的
优化解题思路
⼀边寻找⽬的地，⼀边记录它和起始点的距离（也就是步数）
当发现从某个⽅向过来所需要的步数更少，则更新到这个点的步数
如果发现步数更多，则不再继续尝试
情况⼀：从某⽅向到达该点所需要的步数更少则更新
情况⼆：从各⽅向到达该点所需要的步数都更多则不再尝试
void solve(int maze[][]) {
for (int i = 0; i < maze.length; i++) {
for (int j = 0; j < maze[0].length; j++) {
if (maze[i][j] == 0 && !(i == A[0] && j == A[1])) {
maze[i][j] = Integer.MAX_VALUE;
}
}
}
dfs(maze, A[0], A[1]);
if (maze[B[0]][B[1]] < Integer.MAX_VALUE) {
print("Shortest path count is: " +
maze[B[0]][B[1]]);
} else {
print("Cannot find B!");
}
}
步骤
1：除A之外的所有0都⽤Max替换
2：对矩阵进⾏DFS遍历
3：判读是否抵达B点
dfs函数实现
void dfs(int maze[][], int x, int y) {
if (x == B[0] && y == B[1]) return;
for (int d = 0; d < 4; d++) {
int i = x + dx[d], j = y + dy[d];
if (isSafe(maze, i, j) && maze[i][j] > maze[x][y] + 1) {
maze[i][j] = maze[x][y] + 1;
dfs(maze, i, j);
}
}
}
分析
1：判断是否找到到⽬的地B
2：从四个⽅向上进⾏尝试
3：下个点步数是否⼤于当前点步数+1
4：是则更新下个点步数，并继续DFS
当程序运行完毕之后，矩阵的最终结果为：
2.2 广度优先搜索算法
⼴度优先搜索简称BFS
⼴度优先搜索⼀般⽤来解决最短路径的问题
⼴度优先的搜索是从起始点出发，⼀层⼀层地进⾏
每层当中的点距离起始点的步数都是相同的
双端BFS
同时从起始点和终点开始进⾏的 ⼴度优先的搜索称为双端BFS
双端BFS可以⼤⼤地提⾼搜索的效率
例如，想判断社交应⽤程序中两个⼈之间需要经过多少朋友介绍才能互相认识
假设我们有这么⼀个图，⾥⾯有A, B, C, D, E, F, G, H 8个顶点，点和点之间的联系如下图所示：
如何对这个图进⾏⼴度优先的遍历呢？
- ⼴度优先遍历需要借⽤的数据结构是队列（Queue）
- 队列特点是先进先出（FIFO）
步骤
第一步，选择一个起始顶点，我们从顶点A开始，把A压入队列，标记它为访问过；
第二步，从队列的头取出顶点A，打印输出到结果中，同时，把与它相连的尚未被访问过的点按照字母顺序压入队列，即B，D，G，同时，把它们都标记为访问过，防止它们被重复的添加到队列中；
第三步，从队列的头取出顶点B，打印输出它，同时，把与它相连的尚未被访问过的点按照字母顺序压入队列，即E，F，同时，把它们都标记为访问过，防止它们被重复的添加到队列中；
第四步，继续从对头取出顶点D，打印输出它，这个时候发现与D相连的顶点A和F都被标记过了，所以就不要压入了；
第五步，队列的头是顶点G，打印输出它，同样的，G周围的点都被标记过，不做处理；
第六步，队列的头是顶点E，打印输出它，同样的，E周围的点都被标记过，不做处理；
第七步，队列的头是顶点F，打印输出它，将C压入队列，并且标记C为访问过；
第八步，队列的头是顶点C，打印输出它，将H压入队列，并且标记H为访问过；
第九步，队里只剩下H了，将它移出，打印输出它，发现它的邻居都被访问了，不做处理；
最后一步，队列为空，表示所有元素都被处理了，程序结束。
如何运⽤⼴度优先搜索在迷宫中寻找最短的路径？
void bfs(int[][] maze, int x, int y) {
Queue<Integer[]> queue = new LinkedList<>();
queue.add(new Integer[] {x, y});
while (!queue.isEmpty()) {
Integer[] pos = queue.poll();
x = pos[0]; y = pos[1];
for (int d = 0; d < 4; d++) {
int i = x + dx[d], j = y + dy[d];
if (isSafe(maze, i, j)) {
maze[i][j] = maze[x][y] + 1;
queue.add(new Integer[] {i, j});
if (i == B[0] && j == B[1]) return;
}
}
}
}
步骤
1：创建⼀个队列，将起始点加⼊队列中
2：只要队列不为空，就⼀直循环下去
3：从队列中取出当前要处理的点
4：在四个⽅向上进⾏BFS搜索
5：判断⼀下该⽅向上的点是否已经访问过了
6：被访问过，则记录步数，并加⼊队列中
7：找到⽬的地后⽴即返回
BFS复杂度分析
由于BFS是图论⾥的算法，分析利⽤BFS解题的复杂度时，应当借⽤图论的思想，图有两种表示⽅式：
‣ 邻接表（图⾥有V个顶点，E条边）
每个顶点都需要被访问⼀次，因此时间复杂度是O(V)，在访问每个顶点的时候，与它相连的顶点（也就是每条边）也都要被访问⼀次，所以加起来就是O(E)，因此整体时间复杂度就是O(V+E)。
‣ 邻接矩阵（图⾥有V个顶点，E条边）
由于有V个顶点，每次都要检查每个顶点与其他顶点是否有联系，因此时间复杂度是O(V2)
利⽤BFS在迷宫⾥找⼀条路径
由于迷宫是⽤矩阵表示，所以假设它是⼀个M⾏N列邻接矩阵
‣ 时间复杂度为O(M × N)
因为⼀共有M × N个顶点，所以时间复杂度就是O(M × N)
‣ 空间复杂度为O(M × N)
BFS需要借助⼀个队列，所有顶点都要进⼊队列⼀次，从队列弹出⼀次在最坏的情况下，空间复杂度是O(V)，即O(M × N)
从A⾛到B最多允许打通3堵墙，求最短路径的步数
暴⼒解题法
⾸先枚举出所有拆墙的⽅法，假设⼀共有K堵墙在当前的迷宫⾥，现在最多允许拆3堵墙，意味着可以选择不拆、只拆⼀堵墙、两堵墙或三堵墙,那么⼀共有这么多种组合⽅式：
在这么多种情况下分别进⾏BFS，整体的时间复杂度就是O(n2xKw)从中找到最短的那条路径，很显然，从中找到最短的那条路径是⾮常没有效率的做法
如何将BFS的数量减少？
在不允许打通墙的情况下，只有⼀个⼈进⾏BFS搜索，时间复杂度是n2
允许打通⼀堵墙的情况下，分身为两个⼈进⾏BFS搜索，时间复杂度是2n2
允许打通两堵墙的情况下，分身为三个⼈进⾏BFS搜索，时间复杂度是3n2
允许打通三堵墙的情况下，分身为四个⼈进⾏BFS搜索，时间复杂度是4n2
关键问题
如果第⼀个⼈⼜遇到了⼀堵墙，那么他是否需要再次分身呢？不能
第⼀个⼈怎么告诉第⼆个⼈可以去访问这个点呢？把这个点放⼊到队列中就好了
如何让4个⼈在独⽴的平⾯⾥搜索呢？利⽤⼀个三维矩阵记录每个层⾯⾥的点即可
代码实现
int bfs(int[][] maze, int x, int y, int w) {
int steps = 0, z = 0;
Queue<Integer[]> queue = new LinkedList<>();
queue.add(new Integer[] {x, y, z});
queue.add(null);
boolean[][][] visited = new boolean[N][N][w + 1];
visited[x][y][z] = true;
while (!queue.isEmpty()) {
Integer[] pos = queue.poll();
if (pos != null) {
x = pos[0]; y = pos[1]; z = pos[2];
if (x == B[0] && y == B[1]) {
return steps;
}
for (int d = 0; d < 4; d++) {
int i = x + dx[d], j = y + dy[d];
if (!isSafe(maze, i, j, z, visited)) {
continue;
}
int k = getLayer(maze, w, i, j, z);
if (k >= 0) {
visited[i][j][k] = true;
queue.add(new Integer[] {i, j, k});
}
}
} else {
steps++;
if (!queue.isEmpty()) {
queue.add(null);
}
}
}
return -1;
}
代码分析
1：初始化变量，steps记录步数，z记录Level⽤⼀个队列来存储要处理的各个层⾯的点三维布尔数组记录各层⾯点的被访问情况
2：只要队列不为空就⼀直循环下去
3：取出当前点，如遇⽬的地则返回步数
4：如果不是，则朝四个⽅向尝试下⼀步
5：getLayer函数判断是否遇到可打通的墙壁
6：若当前点是null，则继续下⼀步
getLayer的思想
如果当前遇到的是⼀堵墙，判断所打通的墙壁个数是否已经超出规定，如果没有，就将其打通，否则返回-1。
如果当前遇到的不是⼀堵墙，就继续在当前的平⾯⾥进⾏BFS。
核心代码
int getLayer(int[][] maze, int w, int x,int y, int z) {
if (maze[x][y] == -1) {
return z < w ? z + 1 : -1;
}
return z;
}
3. 总结
本文章是小朱近日刷算法题，看视频之后做的一些笔记和总结，希望大家有所收获，不足之处，请指正，如果对你有帮助可以点赞加收藏。
