BFS算法详解：原理、实现与应用场景
BFS算法详解：原理、实现与应用场景
广度优先搜索（BFS）是一种用于图形数据结构的遍历算法，它从给定的起始顶点开始，以广度优先的方式逐层地搜索图中的节点。本文将详细介绍BFS算法的基本概念、工作原理、时间复杂度和空间复杂度分析，以及其应用场景。同时，本文还将讨论BFS与DFS（深度优先搜索）的区别，并提供BFS算法的实现框架。
（一）BFS算法介绍
- 广度优先搜索（BFS）的定义与基本概念
广度优先搜索（BFS）是一种用于图形数据结构（包括树，因为树是一种特殊的图）的遍历算法。它从给定的起始顶点开始，以广度优先的方式逐层地搜索图中的节点。简单来说，BFS 先访问起始顶点的所有相邻顶点，然后再依次访问这些相邻顶点的相邻顶点，以此类推，就像水波一样一层一层地向外扩散。
例如，把图想象成一个迷宫，BFS 的过程就像是从入口开始，先探索入口周围的所有通道，然后再探索这些通道所能到达的新的通道，直到遍历完整个迷宫。
- BFS 的工作原理
使用队列数据结构：BFS 利用队列来实现。队列是一种先进先出（FIFO）的数据结构。首先将起始顶点放入队列。然后，当队列不为空时，取出队首元素，访问该元素，并将其所有未访问的相邻顶点放入队列。重复这个过程，直到队列为空。
标记已访问节点：为了避免重复访问节点，需要一个标记机制。通常可以使用一个布尔数组来记录每个节点是否已经被访问。当访问一个节点时，将其对应的数组元素标记为已访问。
示例 - 简单图的 BFS 遍历：假设有一个无向图，顶点集合为，边集合为。从顶点开始进行 BFS 遍历。首先将放入队列，标记为已访问。然后取出队首元素，访问，并将的相邻顶点和放入队列，标记和为已访问。接着取出队首元素，访问，将的相邻顶点放入队列，标记为已访问。再取出队首元素，访问，将的相邻顶点放入队列，标记为已访问。最后依次取出并访问和，直到队列空，完成 BFS 遍历。
- BFS 的时间复杂度和空间复杂度
时间复杂度：在最坏情况下，对于一个包含个顶点和条边的图，BFS 的时间复杂度是。这是因为每个顶点和每条边最多被访问一次。如果图是连通的，时间复杂度近似为，因为。
空间复杂度：空间复杂度主要取决于队列的大小和用于标记已访问节点的数组大小。在最坏情况下，队列中可能需要存储所有的顶点，所以空间复杂度是。如果图是稀疏的（边数远小于顶点数的平方），并且使用邻接表来存储图，那么空间复杂度可以降低。
- BFS 的应用场景
寻找最短路径（无权图）：在无权图中，BFS 可以用来寻找从起始顶点到其他顶点的最短路径。例如，在一个社交网络中，如果两个人之间的关系可以看作是边，那么可以用 BFS 来计算两个人之间的最短人脉关系。
遍历或搜索网络结构：如网页爬虫，从一个初始网页开始，通过超链接访问其他网页，BFS 可以保证按照广度优先的方式访问网页，使得搜索能够比较均匀地覆盖网络。
检测图的连通性：通过 BFS 可以判断一个图是否是连通的。如果从一个顶点开始 BFS 遍历后，所有的顶点都被访问到，那么这个图是连通的；否则，这个图是非连通的。
解决一些状态空间搜索问题：比如在一些游戏中，寻找从初始状态到目标状态的最短操作步骤，只要将游戏状态抽象成图中的顶点，操作步骤抽象成边，就可以使用 BFS 来求解。
（二）BFS算法解题框架
这里注意这个 while 循环和 for 循环的配合,while 循环控制一层一层往下走， for 循环利用 sz 变量控制从左到右遍历每一层二叉树节点来。
（三）疑问
1、为什么 BFS 可以找到最短距离，DFS 不行吗?
首先，你看 BFS 的逻辑，depth 每增加一次，队列中的所有节点都向前迈一步，这保证了第一次到达终点的时候，走的步数是最少的。
DFS 不能找最短路径吗?其实也是可以的，但是时间复杂度相对高很多。你想啊、DFS 实际上是靠递归的堆栈记录走过的路径、你要找到最短路径，肯定得把二叉树中所有树权都探索完才能对比出最短的路径有多长对不对?而 BFS 借助队列做到一次一步「齐头并进」，是可以在不遍历完整棵树的条件下找到最短距离的。
形象点说，DFS 是线，BFS 是面;DFS 是单打独斗，BFS 是集体行动。这个应该比较容易理解吧
2、既然 BFS 那么好，为啥 DFS 还要存在!
BFS 可以找到最短距离，但是空间复杂度高，而 DES 的空间复杂度较低
还是拿刚才我们处理二叉树问题的例子，假设给你的这个二叉树是满二叉树，节点数为 N，对于 DFS 算法来说，空间复杂度无非就是递归堆栈，最坏情况下顶多就是树的高度，也就是 0(logN)。
但是你想想 BFS 算法，队列中每次都会储存着二叉树一层的节点，这样的话最坏情况下空间复杂度应该是树的最底层节点的数量，也就是 N/2，用 Big◎ 表示的话也就是 0(N)。
由此观之，BFS 还是有代价的，一般来说在找最短路径的时候使用 BFS，其他时候还是 DFS 使用得多一些(主要是递归代码好写)