专栏首页开心的学习之路广度优先搜索(BFS)

广度优先搜索(BFS)

广度优先搜索(BFS)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。

算法:

1、构造由根组成的队列Q;

2、If Q的第一个元素x是目标节点 Then 停止;

3、从Q中删除x, 把x的所有子节点加入Q的末尾;

4、If Q空 Then 失败   Else goto 2.

举例:

八数码问题:

------输入:具有8个编号小方块的魔方

------输出:移动系列,经过这些移动,魔方达到如下状态

分析:

        每一个空有两种移动方法,可以转化成树形问题,按照算法搜索到红色部分跳出循环,输出解。如图

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 深度优先搜索(DFS)

    深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只...

    刘开心_1266679
  • 基于协同过滤的推荐引擎(理论部分)

    记得原来和朋友猜测过网易云的推荐是怎么实现的,大概的猜测有两种:一种是看你听过的和收藏过的音乐,再看和你一样听过这些音乐的人他们喜欢听什么音乐,把他喜欢的你没听...

    刘开心_1266679
  • 算法训练 Hanoi问题

      如果将课本上的Hanoi塔问题稍做修改:仍然是给定N只盘子,3根柱子,但是允许每次最多移动相邻的M只盘子(当然移动盘子的数目也可以小于M),最少需要多少次?...

    刘开心_1266679
  • Stanford机器学习笔记-7. Machine Learning System Design

    7 Machine Learning System Design Content   7 Machine Learning System Design  ...

    llhthinker
  • 转录组数据分析的4个维度认识(数据分析继续免费哦)

    昨天接到大神任务总结下转录组分析的四个维度,最近我正好也想理清楚下转录组分析的知识点,以便更好地理解RNA-Seq数据的分析结果和方法原理,因此趁周末有些许空暇...

    生信技能树
  • 操作系统演进的五个阶段(9k字)

    科学Sciences导读:纵观计算机历史,操作系统与计算机硬件的发展息息相关。本书从操作系统演进的五个阶段(9k字)、早期操作系统的发展阶段(10k字)、硬件兼...

    秦陇纪
  • 白底黑字or黑底白字,眼睛更喜欢哪一个?

    导语 | 白纸黑字是用户一贯的阅读习惯。在实际的使用场景中,黑底白字和白底黑字哪一种阅读体验会更好?对于我们的眼睛来说,哪一种搭配方式又会更舒适呢? 在人们的...

    腾讯大讲堂
  • 白底黑字or黑底白字,眼睛更喜欢哪一个?

    腾讯大讲堂
  • 从拜占庭将军问题看:区块链「 共识算法 」

    而由于地域上特殊原因,你们这10支军队不能集合在一起单点进攻,必须在分开的状态下同时包围攻击敌国。如果是单支军队单独进攻的话是毫无胜算的,除非有至少有6支军队同...

    奎哥
  • 文本属性,边界圆角,背景属性,精灵图案例

    整体设置font: bold 10px/300px '黑体', 'Arial'; 分别是字重,字体大小,行高,字族,顺序可以交换不影响

    小小咸鱼YwY

扫码关注云+社区

领取腾讯云代金券