广度优先搜索 - 宽度优先搜索 - 横向优先搜索 (breadth-first search，BFS)

1. 广度优先搜索 - 宽度优先搜索 - 横向优先搜索 (breadth-first search，BFS)

depth-first search，DFS：深度优先搜索
breadth-first search，BFS：广度优先搜索

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a search key), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
广度优先搜索 (BFS) 是用于遍历或搜索树或图形数据结构的算法。它从树的根部 (或图的某个任意节点，有时称为搜索关键字) 开始，并在移至下一个深度级别的节点之前先探索当前深度的所有邻居节点。

广度优先搜索 - 宽度优先搜索 - 横向优先搜索 (breadth-first search，BFS) 是一种图形搜索算法。BFS 是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用 open-closed 表。

It uses the opposite strategy as depth-first search, which instead explores the node branch as far as possible before being forced to backtrack and expand other nodes.
它使用与深度优先搜索相反的策略，而是在*回溯和扩展其他节点之前，尽可能地探索节点分支。

以德国城市为示例的地图。城市间有数条道路相连接。(An example map of Southern Germany with some connections between cities.)

从法兰克福开始运行广度优先搜索算法，所产生的广度优先搜索算法树。(The breadth-first tree obtained when running BFS on the given map and starting in Frankfurt.)

广度优先搜索算法的动画示例 (Animated example of a breadth-first search) - 达到覆盖面积的作用

BFS 是一种盲目搜索法，目的是系统地展开并检查图中的所有节点，以找寻结果。它并不考虑结果的可能地址，彻底地搜索整张图，直到找到结果为止。BFS 并不使用经验法则算法。

从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实现里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中 (例如队列或链表)，而被检验过的节点则被放置在被称为 closed 的容器中。(open-closed 表)

animate [ˈænɪmeɪt]：vt. 使有生气，使活泼，鼓舞，推动 adj. 有生命的

广度优先搜索 (BFS) 是图的一种遍历方式，它以广度优先进行搜索。简言之就是先访问图的顶点，然后广度优先访问其邻接点，然后再依次进行被访问点的邻接点，一层一层访问，直至访问完所有点，遍历结束。

1.1 无向图的广度优先搜索过程

遍历结果：A -> C -> D -> F -> B -> G -> E

1.2 有向图的广度优先搜索

遍历结果：A -> B -> C -> E -> F -> D -> G

2. 深度优先搜索 - 广度优先搜索

• 深度优先搜索占内存少但速度较慢，广度优先搜索占内存多但速度较快。
• 深度优先搜索与广度优先搜索的控制结构和产生系统很相似，唯一的区别在于对扩展节点选取上。
• 深度优先搜索与广度优先搜索两种算法每次都扩展一个节点的所有子节点，不同的是，深度优先下一次扩展的是本次扩展出来的子节点中的一个，而广度优先扩展的则是本次扩展的节点的兄弟点。在具体实现上为了提高效率，所以采用了不同的数据结构。

2.1 深度优先搜索 (depth-first search，DFS)

深度优先搜索用栈 (stack) 来实现，整个过程可以看做一个倒立的树形。

1. 把根节点压入栈中。
2. 每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。
3. 找到所要找的元素时结束程序。
4. 如果遍历整个树还没有找到，结束程序。

2.2 广度优先搜索 - 宽度优先搜索 - 横向优先搜索 (breadth-first search，BFS)

广度优先搜索使用队列 (queue) 来实现，整个过程可以看做一个倒立的树形。

1. 把根节点放到队列的末尾。
2. 每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
3. 找到所要找的元素时结束程序。
4. 如果遍历整个树还没有找到，结束程序。

3. 空间复杂度

说法一
所有节点都必须被存储，BFS 的空间复杂度为 $O(|V|+|E|)$O(∣V∣+∣E∣)，其中 $|V|$∣V∣ 是节点的数目，而 $|E|$∣E∣ 是图中边的数目。

说法二
BFS 的空间复杂度为 $O(B^M)$O(BM)，其中 $B$B 是最大分支系数，而 $M$M 是树的最长路径长度。由于对空间的大量需求，BFS 并不适合解非常大的问题。对于类似的问题，应用 IDDFS 以达节省空间的效果。

4. 时间复杂度

最差情形下，BFS 必须查找所有到可能节点的所有路径，因此其时间复杂度为 $O(|V|+|E|)$O(∣V∣+∣E∣)，其中 $|V|$∣V∣ 是节点的数目，而 $|E|$∣E∣ 是图中边的数目。

5. 完全性

广度优先搜索算法具有完全性。无论图形的种类如何，只要目标存在，则 BFS 一定会找到。若目标不存在，且图为无限大，则 BFS 将不收敛 (不会结束)。

6. 最佳解

若所有边的长度相等，广度优先搜索算法是最佳解 - 亦即它找到的第一个解，距离根节点的边数目一定最少。但对一般的图来说，BFS 并不一定回传最佳解。这是因为当图形为加权图 (亦即各边长度不同) 时，BFS 仍然回传从根节点开始，经过边数目最少的解。而这个解距离根节点的距离不一定最短。这个问题可以使用考虑各边权值，BFS 的改良算法成本一致搜索法来解决。若非加权图形，则所有边的长度相等，BFS 就能找到最近的最佳解。

7. 广度优先搜索算法的应用

广度优先搜索算法能用来解决图论中的许多问题，例如：

• 查找图中所有连接组件 (Connected Component)。一个连接组件是图中的最大相连子图。
• 查找连接组件中的所有节点。
• 查找非加权图中任两点的最短路径。
• 测试一图是否为二分图。
• (Reverse) Cuthill-McKee 算法

7.1 查找连接组件

由起点开始，运行广度优先搜索算法后所经过的所有节点，即为包含起点的一个连接组件。

References

https://en.wikipedia.org/wiki/Breadth-first_search
https://en.wikipedia.org/wiki/Depth-first_search