数据结构与算法(四) 广度优先搜索 上

前言

本篇文章继续来学习广度优先搜索算法（Broad-First-Search，BFS）

目录

1、本质

2、核心

3、框架

4、例题

5、优化

正文

1、本质

广度优先搜索本质上还是遍历整个搜索空间，找到给定问题的解

实际上也是一种暴力搜索算法，不过其中的实现细节和优化细节还是值得探讨的

与深度优先算法略有不同，广度优先搜索是同时推进各搜索路径的（雨露均沾）

下面以图的遍历作为例子，直观上感受下广度优先搜索是一个怎么样的搜索过程

假设初始节点为 1，目标节点为 9，则具体遍历步骤如下：

2、核心

广度优先搜索的实现过程很容易理解，直观上感受就是每次从搜索边界向周围扩散一圈

更具体来说，我们需要维护一组节点，每次取出全部节点对其进行处理，然后将相邻的节点重新加入维护

直至遍历完所有节点、或者到达目标节点、或者满足结束条件时才停止上述过程

对标深度优先搜索，广度优先搜索也有几个核心的概念，分别是：

• 当前节点集合：目前维护的节点集合，是上一步的相邻节点
• 相邻节点集合：当前节点的相邻节点，是下一步的当前节点
• 结束条件：表示遍历到哪些节点停止
• 约束条件：表示哪些节点不可以遍历

对比深度优先搜索，广度优先搜索可以更快地找到抵达目标节点的最短路径

但是作为代价，广度优先搜索具有更高的空间复杂度，因此在使用过程中，需要根据实际情况进行选择

3、框架

广度优先搜索算法可以使用队列实现，大致过程描述如下

首先将初始节点加入队列，然后开始循环，直至队列为空

每次循环从队列取出所有节点并对其处理，然后再将每个节点的相邻节点加入队列

在这个过程中，还需要使用集合来标记已被处理过的元素，避免重复访问

具体的代码框架如下：

def bfs(初始节点):
  初始化步数为零
  初始化队列为空
  初始化集合为空
  将初始节点加入队列
  将初始节点加入集合
  while 队列不为空:
    for _ in 队列.长度():
          元素 = 队列.出队()
      if  元素能满足结束条件:
        表示当前元素合法，返回对应结果
      if  元素不满足约束条件:
        表示当前元素非法，跳过当前元素
      for 相邻元素 in 元素.相邻元素():
        if  相邻元素不在集合中:
          队列.入队(相邻元素)
          集合.加入(相邻元素)
    步数 += 1