广度优先算法 - Thu, Jun 11, 2020

广度优先算法

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是最大分支系数。