广度优先算法

  1. 1. 概述
  2. 2. 实现方法
  3. 3. 复杂度

广度优先算法

1. 概述

BFS也叫分支界限法。
BFS是一种盲目搜索法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能地址,彻底地搜索整张图,直到找到结果为止。
BFS是一种空间换时间的算法。

2. 实现方法

  1. 首先将根节点放入队列中。
  2. 从队列中取出第一个节点,并检验它是否为目标。
    • 如果找到目标,则结束搜索并回传结果。
    • 否则将它所有尚未检验过的直接子节点加入队列中。
  3. 若队列为空,表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。
  4. 重复步骤2。

3. 复杂度

  • 时间复杂度
    $${\displaystyle O(|V|+|E|)}$$
    ${\displaystyle |V|}$是节点的数目,${\displaystyle |E|}$是边的数目。

  • 空间复杂度
    $${\displaystyle O(|V|+|E|)}或 {\displaystyle O(B^{M})}$$
    ${\displaystyle |V|}$是节点的数目,${\displaystyle |E|}$是边的数目,B是最大分支系数。


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 wind.kaisa@gmail.com

💰

×

Help us with donation