算法之广度优先搜索

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 算法之广度优先搜索

算法之广度优先搜索

戳上面的蓝字关注我们哦!

算法之广度优先搜索

本文作者:丹丘生

文末阅读原文获取文中示例代码

一、引言

上一次介绍的算法是深度优先搜索,如果忘记了什么是深度优先搜索,请看上篇:

这次我们来研究一下广度优先搜索,看看怎么理解以及写出这个算法

这个算法需要数据结构的基础–队列,如果没有这个基础的同学去恶补一下。

二、小小问题

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方法
    }
    
    
    //  设置队列
    QueueNode que = new LinkedListNode();
    //起点进队列
    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,对于我们的话,直接使用即可。

    四、总结

  • BFS数据结构是队列
  • BFS适用于树的高度不深,子节点的数量不多。否则耗内存存储节点数据。也就是队列数据的存储。
  • DFS寻找有解,很难寻找最优解;但是没有BFS的缺点,耗内存。
  • BFS适用于树的高度不深,子节点的数量不多。否则耗内存存储节点数据。也就是队列数据的存储。

    五、小试牛刀

    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)

  • 关注算法文摘,修炼开发内功

    算法之广度优先搜索

    始发于微信公众号: 后端技术精选

    本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

    转载声明:转载请注明出处,本技术博客是本人原创文章

    本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

    原文链接:blog.ouyangsihai.cn >> 算法之广度优先搜索


     上一篇
    PL,SQL Developer连接虚拟机数据库(图文详解) PL,SQL Developer连接虚拟机数据库(图文详解)
    本文系投稿,作者:Web项目聚集地微信号:web_resource 知音专栏       Web项目聚集地的朋友求助关于PL/SQL Developer连接虚拟机Oracle数据库的教程,他说自己操作过程遇到很多错误,可以说操
    2021-04-06
    下一篇 
    TCP之三次握手四次挥手 TCP之三次握手四次挥手
    作者:gyl-coder,本文系投稿原作者有一个非常棒的个人博客,欢迎围观 知音专栏 TCP报文格式TCP提供一种面向连接的,可靠的字节流服务。 TCP首部的数据格式如下。(如果不计任选字段,通常是20个字节) 字段分析 源端口
    2021-04-06