首页 > 其他分享 >BFS(Breath First Search 广度优先搜索)

BFS(Breath First Search 广度优先搜索)

时间:2024-11-01 15:20:09浏览次数:2  
标签:Node BFS Search String bfs Breath new null cur

@

目录

一、知识及框架

  1. BFS算法都是用 “队列” 结构
  2. BFS和DFS最主要区别:bfs找到的路径一定是最短的,但代价是空间复杂度比dfs大很多
  3. bfs本质:一幅图,从起点到终点,求最短路径
  4. bfs空间复杂度高,而dfs空间复杂度较低
  5. 形象点说:dfs是线,bfs是面,dfs是单打独斗,bfs是集体行动
  6. dfs和bfs的时间复杂度都是O(N)
  7. BFS干的事:从起点start到终点target的最近距离
  8. BFS应用举例:走迷宫、连连看......

※ 思考问题1:为什么bfs、dfs都可以找到最短距离,但一般都使用bfs方法,而不用dfs呢?
答:bfs是齐头并进,一旦找到终点就不找了,而dfs需要全遍历后才知道最短路径

※ 思考问题2:既然bfs那么好,为啥dfs还需要存在?
答:bfs代价太大,除找最短路径用bfs,其他情况推荐dfs

BFS框架:

二、案例说明

说明:Node节点class对象代码请查看上一篇文章,https://blog.csdn.net/a924382407/article/details/118394577

二叉树

		/*   a1:↓                           a2:↓                  a3:↓
                1                               1                     1
               / \                                                   / \
              2   3                                                 2   3
             / \
            4   5
               /
              6
         */
        Node a1 = new Node(1, new Node(2, new Node(4), new Node(5, new Node(6), null)), new Node(3));
        Node a2 = new Node(1, null, null);
        Node a3 = new Node(1, new Node(2, null, null), new Node(3, null, null));

main函数

public static void main(String[] args){
		//问题3.1:使用bfs计算二叉树的最小高度
        System.out.println("使用bfs计算二叉树的最小高度:" + bfsMinDepth(a1));
        //问题3.2:解开密码锁的最少次数
        System.out.println("解开密码锁的最少次数:" + openLock(new String[]{"8887", "7789"}, "8888"));
}

案例1:使用bfs计算二叉树的最小高度

	//问题3.1:使用bfs计算二叉树的最小高度
    public static int bfsMinDepth(Node root) {
        if (root == null) return 0;
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        //root本身就是一层,将depth初始化为1
        int depth = 1;

        while (!q.isEmpty()) {
            int sz = q.size();
            //将当前队列中所有节点想四周扩散
            for (int i = 0; i < sz; i++) {
                Node cur = q.poll();
                //判断是否到达终点
                if (cur.left == null && cur.right == null) return depth;
                //将cur的相邻节点加入队列
                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
            }
            //重点:这里增加步数
            depth++;
        }
        return depth;
    }

案例2:解开密码锁的最少次数,要求:请写一个算法,初始状态为0000,拨出target的最少次数,其中避免出现deadends中的包含的任意一个死亡密码,如果永远无法拨出target,则返回-1

	/**
     * 问题3.2:解开密码锁的最少次数
     *      要求:请写一个算法,初始状态为0000,拨出target的最少次数,其中避免出现deadends中的包含的任意一个死亡密码,如果永远无法拨出target,则返回-1
     */
    //将s[j]向上拨动一次
    public static String plusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '9') {
            ch[j] = '0';
        } else {
            ch[j] += 1;
        }
        return new String(ch);
    }
    
    //将s[j]向下拨动一次
    public static String minusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '0') {
            ch[j] = '9';
        } else {
            ch[j] -= 1;
        }
        return new String(ch);
    }
    
    /**
     * openLock
     * @param deadends 死亡数字
     * @param target  目标密码
     * @return 次数
     */
    public static int openLock(String[] deadends, String target) {
        //记录需要跳过的死亡密码
        Set<String> deads = new HashSet<>();
        for (String s : deadends) deads.add(s);
        //记录已经穷举过的密码,防止走回头路
        Set<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        //从起点开始启动广度搜先搜索
        int step = 0;
        q.offer("0000");
        visited.add("0000");

        while (!q.isEmpty()) {
            int sz = q.size();
            //将当前队列中所有节点向四周扩散
            for (int i = 0; i < sz; i++) {
                String cur = q.poll();
                //判断密码是否合法,是否到达终点
                if (deads.contains(cur)) continue;
                if (cur.equals(target)) return step;
                //将一个节点的未遍历相邻节点加入队列
                for (int j = 0; j < 4; j++) {
                    String up = plusOne(cur, j);
                    if (!visited.contains(up)) {
                        q.offer(up);
                        visited.add(up);
                    }
                    String down = minusOne(cur, j);
                    if (!visited.contains(down)) {
                        q.offer(down);
                        visited.add(down);
                    }
                }
            }
            //重点:增加步数
            step++;
        }
        //如果穷举完都没找到目标密码,那就是找不到了
        return -1;
    }

本人其他文章链接

1.单链表题+数组题(快慢指针和左右指针)

2.BFS(Breath First Search 广度优先搜索)

3.”回溯算法“框架及练习题

4.JAVA 二叉树面试题

标签:Node,BFS,Search,String,bfs,Breath,new,null,cur
From: https://www.cnblogs.com/bigcat26/p/18520342

相关文章

  • 【1】Elasticsearch 30分钟快速入门
    文章目录一、Elasticsearch基本概念及工作原理(一)基本概念(二)工作原理二、Elasticsearch原生RESTful方式的增删改查(一)创建索引(二)插入文档(三)查询文档(四)更新文档(五)删除文档(六)删除索引三、PythonSDK实现增删改查(一)安装ElasticsearchPythonSD......
  • Elasticsearch (ES) 的 ORM(对象关系映射)库
    Elasticsearch(ES)的ORM(对象关系映射)库有几个常用的选择,主要用于简化与Elasticsearch的交互。以下是一些比较流行的库及其特点:1.Elasticsearch-py这是Elasticsearch的官方Python客户端库,不是传统意义上的ORM,但它提供了与Elasticsearch进行交互的丰富API。你可以......
  • Linux Docker 部署 Elasticsearch (ES) 集群详解教程
    1.安装Docker首先,确保你的Linux系统上已经安装了Docker。如果尚未安装,可以通过以下命令进行安装:sudoyuminstall-yyum-utilssudoyum-config-manager--add-repohttps://download.docker.com/linux/centos/docker-ce.reposudoyuminstalldocker-cedocker-ce......
  • 每日OJ题_牛客_AB20走迷宫_BFS_C++_Java
    目录牛客_AB20走迷宫_BFS题目解析C++代码Java代码牛客_AB20走迷宫_BFS走迷宫_牛客题霸_牛客网(nowcoder.com)描述:        给定一个n×m的网格,在网格中每次在不超过边界的情况下可以选择向上、向下、向左、向右移动一格。网格中的一些格子上放置有障碍物,放有......
  • AEER-Applied Ecology and Environmental Research
    @目录一、征稿简介二、重要信息三、服务简述四、投稿须知一、征稿简介二、重要信息期刊官网:https://ais.cn/u/3eEJNv三、服务简述生态环境、生物地理学、动物学、植物学、古生物学、生物计量学、生物数学和定量的生态学或多学科农业研究。期刊名称:AppliedEcologyandEn......
  • ElasticSearch知识点小记
    ElasticSearch索引的基本操作#创建索引PUT/index_name可以初始不定义{ "settings":{ //索引设置 "number_of_shards":"1",//索引的分片书决定了索引的并行度和数据分布不可以动态修改 "number_of_replicas":"1",//副本的数量提高了数据的可用性和容错能力可以动态......
  • ElasticSearch - Bucket Script 使用指南
    文章目录官方文档BucketScript官文1.什么是ElasticSearch中的BucketScript?2.适用场景3.BucketScript的基本结构4.关键参数详解5.示例官方示例:计算每月T恤销售额占总销售额的比率百分比示例计算:点击率(CTR)6.注意事项与限制7.最佳实践官方文档ht......
  • 【项目实战】分布式日志搜索系统之数据同步方案(Logstash-input-jdbc、go-mysql-elast
    在构建分布式日志搜索系统时,数据同步是一个核心环节。以下是针对您提出的五种数据同步方案的详细分析:一、Logstash-input-jdbcLogstash是ElasticStack的一部分,用于从各种来源收集数据,并将其发送到Elasticsearch。Logstash-input-jdbc插件允许Logstash从关系型数据库(如My......
  • Rust整合Elasticsearch
    Elasticsearch是什么Lucene:Java实现的搜索引擎类库易扩展高性能仅限Java开发不支持水平扩展Elasticsearch:基于Lucene开发的分布式搜索和分析引擎支持分布式、水平扩展提高RestfulAPI,可被任何语言调用ElasticStack是什么ELK(ElasticStack):Elasticsearch结合Kibana、Log......
  • elasticsearch使用
    1、选择1、ElasticsearchRestTemplate是spring对官方HighLevelRESTClient的封装。2、ElasticSearch8.x弃用了HighLevelRESTClient,移除了JavaTransportClient,推荐使用ElasticsearchJavaAPI(后续使用8的建议使用ElasticsearchJavaAPI)2、ElasticsearchRestTemp......