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

广度优先搜索 Breadth-First Search(BFS)

时间:2024-04-08 13:56:18浏览次数:24  
标签:Breadth Search bfs int qx 结点 BFS TopsCoding &&

问题引入

​ 对于每一个问题,都会有相应的解,在之前的学习中求解的过程,都是以一条条线的形式产生可能解进行筛选验证是否正确。本章节我们来考虑另外一种思路,类似于洪水爆发,从一个源头开始逐渐蔓延开来,直到所有可达的区域都被洪水淹没,所以我们也把这种算法称之为洪泛法。洪泛法会以面的形式同步扩展更多的可行解,进而拓展广度。

​ 单纯的文字描述无法很好的帮助同学们理解上面的说法,认真学完本章节的内容,相信同学们可以很好的理解广度优先搜索算法。

广度优先搜索算法

​ 广度优先搜索(英文:Breadth-First Search,简称BFS)的思路是会优先考虑每种状态和初始状态的距离,也就是与初始状态越接近的情况就会优先考虑。再具体一点:每个时刻(阶段)要做的事情就是从上个时刻(阶段)每个状态扩展出新的状态。

广度优先搜索使用队列或数组模拟实现:先将初始状态加入到空的队列中,然后每次取出队首,找出队首所能扩展到的状态,再将其压入队列;如此反复,直到队列为空。这样就能保证一个状态在被访问时一定是采用的最短路径。

例如洪水从A点爆发(如下左图所示),在每个点都沿着上下左右的方向淹没相邻的点,那么最终整个地图淹没的时间如下右图所示。

把扩展的情况按层次划分,可以得到下图:

可以发现,广搜更适合解决从起始点到目标点的最短路问题。一般来说,题目描述的是求解最少多少步、最短距离、最短时间这种问题可以考虑用广搜求解。

广搜的模板:

​ 本章节例题将以两种解法进行全面充分的学习广度优先搜索的实现方式,增强同学们的理解。
1. 队列(推荐写法)
2. 数组模拟队列(重点学习)

全局状态变量

void bfs(当前结点) 
{
    当前结点入队
    while (队列不为空) 
    {
        取出队首节点作为当前结点
        if (当前节点是目标结点)
            进行相应处理(输出当前解、更新最优解、退出返回等)
        
        for (由当前结点衍生新结点) 
        {
            if (新结点没有访问过 && 需要访问) 
            {
                新结点入队
            }
        }
        //队首结点已衍生完毕,没有用处了
        队首结点出队
    }
}
int main() {
    ...;
    bfs(初始结点);
    ...;
}

广搜在搜索过程中形象化的运行过程:

例题

标签:Breadth,Search,bfs,int,qx,结点,BFS,TopsCoding,&&
From: https://www.cnblogs.com/Yzc-wm/p/18120977

相关文章

  • Elasticsearch 配置与测试分析器 (2)
    一.配置文本分析器(Configuretextanalysis) 默认情况下,Elasticsearch使用standard分析器来进行文本分析,如果使用该分析器,则不用额外的配置。如果不满足,可以使用其它内置分析器,也可以创建自定义的分析器更好的控制,通常在生产实战中都是自定义分析器,方便更好扩展。 ......
  • Elasticsearch,使用scroll实现遍历(分页)查询
    为什么要使用scroll查询在使用es中,当某个index存贮的数据超过10000时,只能查询到10000的数据。因为index.max_result_window默认值是10000。并且使用游标查询可以在一次查询中获取大量文档,并且保持查询快照状态,允许用户多次检索数据而不影响其他并发请求。scroll查......
  • elasticsearch mapping
    1 概念:​ ES中的mapping有点类似与RDB中“表结构”的概念,在MySQL中,表结构里包含了字段名称,字段的类型还有索引信息等。在Mapping里也包含了一些属性,比如字段名称、类型、字段使用的分词器、是否评分、是否创建索引等属性,并且在ES中一个字段可以有对个类型。分词器、评分等概念在......
  • Elasticsearch 认识分词(1)
    一.概述分词是构建倒排索引的重要一环。根据语言不同可以分为英文分词、中文分词等;根据分词实现的不同又分为标准分词器、空格分词器、停用词分词器等。在传统的分词器不能解决特定业务场景的问题时,往往需要自定义分词器。1.1认识分词对于分词操作来说,英语单词......
  • Elasticsearch-定制分词器
    一、内置分词器分词步骤1).characterfilter:在一段文本进行分词之前,先进行预处理,eg:最常见的过滤html标签(hello->hello),&->and(I&you->Iandyou)2).tokenizer:分词,eg:helloyouandme->hello,you,and,me3).tokenfilter:一个个小单词标准化转换lower......
  • 蓝桥杯:七步诗 ← bfs
    【题目来源】https://www.lanqiao.cn/problems/3447/learning/【题目描述】煮豆燃豆苴,豆在釜中泣。本是同根生,相煎何太急?---曹植所以,这道题目关乎豆子!话说赤壁之战结束后,曹操的船舰被刘备烧了,引领军队从华容道撤退,路上遇到了泥泞,道路不通畅,又刮起了大风,没办法,只好让羸弱的......
  • 代码随想录 | 图论 797. 所有可能的路径(dfs) ,200. 岛屿数量 (dfs)200. 岛屿数量 (bfs)
    797.所有可能的路径https://leetcode.cn/problems/all-paths-from-source-to-target/description/List<List<Integer>>res;List<Integer>path;publicList<List<Integer>>allPathsSourceTarget(int[][]graph){res=newA......
  • 使用阿里云试用Elasticsearch学习:1.1 基础入门——入门实践
    阿里云试用一个月:https://help.aliyun.com/search/?k=elastic&scene=all&page=1官网试用十五天:https://www.elastic.co/cn/cloud/cloud-trial-overviewElasticsearch中文文档:https://www.elastic.co/guide/cn/elasticsearch/guide/current/_document_oriented.html控制台......
  • 图的遍历-BFS
    1.BFS遍历BFS算法的思想:对一个无向连通图,在访问图中某一起始顶点v后,由v出发,依次访问v的所有未访问过的邻接顶点w1,w2,w3,…wt;然后再顺序访问w1,w2,w3,…wt的所有还未访问过的邻接顶点;再从这些访问过的顶点出发,再访问它们的所有还未访问过的邻接顶点,……,如此直......
  • python 插值搜索-迭代与递归(Interpolation Search)
             给定一个由n个均匀分布值arr[]组成的排序数组,编写一个函数来搜索数组中的特定元素x。         线性搜索需要O(n)时间找到元素,跳转搜索需要O(?n)时间,二分搜索需要O(logn)时间。插值搜索是对实例二分搜索的改进,其中排序数组中的值是......