广度优先搜索

admin 2022年1月6日01:35:47安全博客评论18 views570字阅读1分54秒阅读模式

算法概念

也称宽度优先搜索,顾名思义,就是将一棵树一层一层往下搜。算法首先搜索和s距离为k的所有顶点,然后再去搜索和S距离为k+l的其他顶点。BFS是一种完备策略,即只要问题有解,它就一定可以找到解。并且,广度优先搜索找到的解,还一定是路径最短的解。但是它盲目性较大,尤其是当目标节点距初始节点较远时,将产生许多无用的节点,因此其搜索效率较低。需要保存所有扩展出的状态,占用的空间大

在程序实现 BFS 时需要考虑以下问题:

  • 队列:用来存储每一轮遍历得到的节点;
  • 标记:对于遍历过的节点,应该将它标记,防止重复遍历。

BFS可用于解决2类问题:

  • 从A出发是否存在到达B的路径;
  • 从A出发到达B的最短路径(这个应该叫最少步骤合理);

框架

1
2
3
4
5
6
7
8
9
BFS()
{
初始化队列
while(队列不为空且未找到目标节点)
{
取队首节点扩展,并将扩展出的节点放入队尾;
必要时要记住每个节点的父节点;
}
}

例题

  1. 计算在网格中从原点到特定点的最短路径长度
  2. 组成整数的最小平方数数量
  3. 最短单词路径

https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E6%90%9C%E7%B4%A2.md

FROM :blog.cfyqy.com | Author:cfyqy

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月6日01:35:47
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  广度优先搜索 http://cn-sec.com/archives/721950.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: