图的广度优先搜索算法

描述

广度优先搜索（Breadth-First Search，简称 BFS）是一种用于遍历或搜索树或图的算法。 这种算法从根节点开始，然后遍历所有[相邻的]节点，之后对于每一个相邻的节点，再遍历 它们未访问过的相邻节点，依次类推，直到所有的节点都被访问过为止。BFS 是一种逐层扩 展节点的搜索策略，即先搜索离起始节点最近的所有节点，然后再搜索下一层的节点。

BFS 的基本步骤

1. 初始化：选择一个起始节点，将其标记为已访问，并放入队列中。
2. 处理队列中的节点：
   1. 从队列中移除第一个节点。
   2. 对于这个节点，访问它所有的邻接点。如果某个邻接点没有被访问过，则标记这个邻 接点为已访问，并将其添加到队列的末尾。
3. loop[2]，直到队列为空。

在实际操作中，为了防止重复访问同一个节点，通常需要使用一个数据结构来记录已经访 问过的节点。此外，队列是实现 BFS 的关键数据结构，因为它是先进先出（FIFO）的数 据结构，能够确保节点按照其被发现的顺序被处理。