|
本文作者：丹丘生 文末阅读原文获取文中示例代码
一、引言 > 上一次介绍的算法是深度优先搜索，如果忘记了什么是深度优先搜索，请看上篇：算法之深度优先搜索 > 这次我们来研究一下广度优先搜索，看看怎么理解以及写出这个算法 > 这个算法需要数据结构的基础--队列，如果没有这个基础的同学去恶补一下。
二、小小问题 Q：在一个二维地图中，从一个点到另一个点的最短路径(从1到0，输入终点位置，输出最少步数) 1 - - - -
- - - - -
- - - - -
- - - 0 -
第一种：采用深度优先搜索呗。 第二种：用广度优先搜索。当然，你会说，我要是会广搜，我就不会看这篇文章了。
2.1 深度优先搜索 看到深度优先搜索，第一反应就是模板套出来 public static void dfs(int step){
if(...){
return;
}
for(...){
...
dfs(step+1);
...
}
}
DFS主要在于当前这步怎么做，然后继续往下，当然前提我们需要判断它这一步有没有走到终点，也就是另一个点的位置。核心的dfs方法之前一直都只是传递一个step（当前步数），现在我们需要判断这一步有没有走到终点，则需要把当前的x和y一并传递到下一个方法里面去，则dfs的方法声明如下： public static void dfs(int x, int y , int step){
...
}
现在，dfs里面的判断是什么呢？因为dfs是基于递归，所以必定有出口，所以出口是什么呢？出口就是终点位置的x和y。当然在满足这个的情况下，我们要继续判断当前到终点的最少步数是不是比最少的步数还要小，如果还要小则更新最少的步数。 // endx是终点的x endy是终点的y
public static void dfs(int x, int y , int step){
if(endx==x && endy==y){ // 判断是否到了终点
if(step < min_step){="">// 判断是否为最小步数
min_step = step
}
return; // 返回
}
for(...){
.....
dfs(....);
......
}
}
现在最重要的问题来了，for循环里面的内容如何填写呢？ 因为当前的点，可以上下左右行走，则对于走向应该有四个方向，上下左右。那我们定义一个二维数组来搞定方向问题。
因为向左y-1，向右y+1,向上x-1,向下x+1 int[][] direction = {{0, -1}, {-1, 0},{0, 1}, {1, 0}};
//左,上,右,下
所以for循环里面，只需要基于当前的点（x,y)上下左右遍历即可。所以for循环里面只需要遍历方向即可。
当然也需要标记当前点是否访问，所以在之后，判断下一步的点是否访问过，没有访问，则标记访问，然后继续递归。。 for(int i = 0 ; i4;i++){
// 计算下一个点的坐标
next_x = x + direction[i][0];
next_y = y + direction[i][1];
// 需要判断下一个点是否越界，有可能超出了边界
// n是数组的行，m是数组的列
if (next_x <>0 || next_x >= n || next_y <>0 || next_y >= m) {
continue;
}
if (result[next_x][next_y] == 0) {// 判断当前点是否访问
result[next_x][next_y] = 1; // 标记当前点访问
dfs(next_x, next_y, step + 1); // 另一个点继续递归
result[next_x][next_y] = 0; // 标记当前点未访问，基于上一步的递归结束
}
}
dfs方法的全部代码如下： // endx是终点的x endy是终点的y
public static void dfs(int x, int y , int step){
if(endx==x && endy==y){ // 判断是否到了终点
if(step < min_step){="">// 判断是否为最小步数
min_step = step
}
return; // 返回
}
for(int i = 0 ; i4;i++){
// 计算下一个点的坐标
next_x = x + direction[i][0];
next_y = y + direction[i][1];
// 需要判断下一个点是否越界，有可能超出了边界
// n是数组的行，m是数组的列
if (next_x <>0 || next_x >= n || next_y <>0 || next_y >= m) {
continue;
}
// result是二维数组用于标记点是否访问，是全局类型
if (result[next_x][next_y] == 0) {// 判断当前点是否访问
result[next_x][next_y] = 1; // 标记当前点访问
dfs(next_x, next_y, step + 1); // 另一个点继续递归
result[next_x][next_y] = 0; // 标记当前点未访问，基于上一步的递归结束
}
}
}
基本上到这里，采用DFS解决这个问题已经完成了，还有一些输入输出，我这里就省略了，其余的就靠大家自己补充了。
2.2 广度优先搜索 Q：深度优先搜索是从某一个点出发，然后遍历方向。选定一个方向，然后再遍历方向....依次类推，直到遇到终点或者遍历完毕。那我们能不能一次性的将周围的点给遍历，然后再遍历周围的点后再得相邻的点遍历呢？重复上面的步骤，这样当遍历周围的点时，我知道是遍历第几层，也就是第几步，直到遇到终点，最少的步数得出。
比如： (0,0)相邻的点是(0,1)和(1,0); 从(0,0)分别到这两个点的步数是1, (0,1)相邻的点是(1,1)和(0,2),(0,0); 从(0,1)分别到这两个点的步数是2.(0,0)已经访问，此时没有必要访问，所以需要在前一步需要标记已经访问, (1,0)相邻的点是(2,1)和(1,1),(0,0); 从(0,1)分别到这两个点的步数是2,(0,0)已经访问，此时没有必要访问，所以需要在前一步需要标记已经访问, (1,1)相邻的点是(2,1)和(1,2),(0,1),(1,0); 从(0,1)分别到这两个点的步数是3;(0,1)已经访问，此时没有必要访问，所以需要在前一步需要标记已经访问,(1,0)已经访问，此时没有必要访问，所以需要在前一步需要标记已经访问,
- - - - A B C D E F G H I J K L - - - - 按照上面的规律，BFS这个二维数据输出，方向从右往左，（有些因为已经遍历便没有写出来） 基于A： ABE 基于B: CF 基于E: I 基于C: DG 基于F: J 基于I: H 基于D： K 基于J: K(已经遍历) 基于H： L
很明显，学过数据结构的可以看出来这是一个先进先出的队列结构; 所以我们的BFS是基于队列实现的。然后对于这个小问题，我们如何解决呢？
遍历每个点的时候，存储当前节点的步数以及当前点的信息(x,y)即可，然后将这个整体信息进队列，然后获取头结点的相邻数据让其进队列，如果它的相邻数据已经进队列完毕，则让头结点出队列，接着再获取头结点信息，获取头结点的相邻数据让其进队列..步骤雷同不再累述。
这里使用的LinkedList,实现了队列的基本操作。具体操作请参考Java API。 节点有几个重要属性，当前坐标x，y和当前节点是第几步可以到达，则类结构如下： static class Node{
int x ;
int y ;
Node parent;
...省略getter/setter方法
}
// 设置队列
Queue que = new LinkedList();
//起点进队列
Node node = new Node();
node.x = startx;
node.y = starty;
node.step = 0;
node.parent = null;
que.add(node);// 起始点进队列
// 将起点的周围的点进队列
for (int i = 0; i <>4; i++) {
int tx = heads.x + direction[i][0];
int ty = heads.y + direction[i][1];
// 判断是否越界
if (tx <>0 || tx >= n || ty <>0 || ty >= m) {
continue;
}
// 判断该点是否为障碍物并且有没有被访问
if (map[tx][ty] == 0 && result[tx][ty] == 0) {
Node next = new Node();
result[tx][ty] = 1;
next.x = tx;
next.y = ty;
next.parent = heads;
next.step = heads.step + 1;
que.add(next);// 进队列
}
// 如果当前点为最终节点
if (tx == endx && ty == endy) {
break; // 退出for循环
}
}
上面只是满足了最简单的起点周围的点进队列，如果周围的点也要参照这个逻辑进行循环遍历得到相邻的点，则加一个出队列的操作循环判断队列是否还有节点即可。修改代码如下： // 以当前点广搜
Node heads; // 头节点
Node resultNode = null;// 终点
while ((heads = que.poll()) != null) {// 判断队列是否还有元素，也就是出队列操作
for (int i = 0; i <>4; i++) {
int tx = heads.x + direction[i][0];
int ty = heads.y + direction[i][1];
// 判断是否越界
if (tx <>0 || tx >= n || ty <>0 || ty >= m) {
continue;
}
// 判断该点是否为障碍物并且有没有被访问
if (result[tx][ty] == 0) {
Node next = new Node();
result[tx][ty] = 1;
next.x = tx;
next.y = ty;
next.parent = heads;
next.step = heads.step + 1;
resultNode = next;
que.add(next);
}
// 如果当前点为最终节点
if (tx == endx && ty == endy) {
flag = 1; // 标志找到
break; // 退出for循环
}
}
if (flag == 1) // 如果找到 退出while循环
break;
}
三、概念 Q：什么是广度优先算法呢？ 广度优先算法简称BFS。它主要是”一层层的“的搜索来进行扩展获取每个点的数据，直到找到某个确定的点。Java已经实现了这种数据结构--Queue，对于我们的话，直接使用即可。
四、总结
五、小试牛刀 1. 海岛淹没，有多少个没有淹没的小岛?(上下左右四个相邻像素中只要有一个方向有海洋，它就会被淹没) ....... .##.... .##.... ....##. ..####. ...###. .......
六、示例代码 - [DFS](https://github.com/danqiusheng/algorithm_practice/blob/master/src/dfs/DFS_4.java) - [BFS](https://github.com/danqiusheng/algorithm_practice/blob/master/src/bfs/BFS_3.java) - [海岛](https://github.com/danqiusheng/algorithm_practice/blob/master/src/bfs/BFS_4.java)
关注算法文摘，修炼开发内功
|
