文章目录

• 广度优先搜索（BFS）算法详解与C++实现
• • BFS的工作原理
  • BFS的实现
  • • C++中BFS的实现
  • BFS的应用场景
  • 注意事项

广度优先搜索（BFS）算法详解与C++实现

广度优先搜索（Breadth-First Search，BFS）是一种遍历或搜索树和图的算法。它从树的根（或图的某一顶点）开始，探索邻近的节点，然后再对每个邻近节点做同样的操作。BFS在搜索最短路径问题、层次遍历树、图的连通性等方面有着广泛的应用。

BFS的工作原理

BFS按照距离起始节点的层数逐层向外扩展，即先访问起始节点，然后是距离起始节点最近的节点，接着是距离起始节点第二近的节点，依此类推。为了实现这种层级的遍历，BFS使用了先进先出（FIFO）的队列结构来存储每层的节点。

BFS的实现

BFS的实现通常依赖于队列数据结构，通过迭代的方式来实现。在开始时，将起始节点放入队列。然后，只要队列不为空，就从队列中移除一个节点，访问它，并将所有未访问过的邻接节点加入队列中。

C++中BFS的实现

以下是使用C++标准库中的队列来实现BFS算法的示例代码：

#include  #include  #include   // 使用队列的方式实现的BFS void BFS(int startVertex, const std::vector>& graph) {     std::vector visited(graph.size(), false);     std::queue queue;      // 标记起始顶点为已访问，并将其入队     visited[startVertex] = true;     queue.push(startVertex);      while (!queue.empty()) {         // 取出队首元素         int vertex = queue.front();         queue.pop();         std::cout << vertex << " ";          // 遍历该顶点的所有邻接点         for (int neighbor : graph[vertex]) {             if (!visited[neighbor]) {                 visited[neighbor] = true;                 queue.push(neighbor);             }         }     } }  int main() {     // 图的邻接表表示     std::vector> graph = {         {1, 2},    // 邻接于节点0         {0, 3, 4}, // 邻接于节点1         {0, 4},    // 邻接于节点2         {1, 5},    // 邻接于节点3         {1, 2},    // 邻接于节点4         {3}        // 邻接于节点5     };      // 从节点0开始进行BFS遍历     std::cout << "BFS starting from vertex 0:\n";     BFS(0, graph);      return 0; } 

在上述代码中，我们先将起始节点标记为已访问并加入队列。在主循环中，我们每次从队列中取出一个节点，访问它，并把所有未访问的邻接节点加入队列中。这个过程一直持续到队列为空，即所有可达节点都被访问。

BFS的应用场景

BFS不仅可以用来遍历图，还有以下的应用：

1. 最短路径：在无权图中找到两点间的最短路径。
2. 连通性测试：检查图中任两个节点之间是否存在路径。
3. 层次遍历：在树结构中按层次遍历节点。
4. 网络爬虫：搜索引擎中的网络爬虫使用BFS来遍历网页。
5. 广播网络：在广播网络中找出最佳的广播接收点。

注意事项

在使用BFS时，需要注意以下几点

#include  #include  #include   // 使用队列实现的BFS函数 void BFS(int startVertex, const std::vector>& graph) {     std::vector visited(graph.size(), false); // 创建一个visited数组，用于跟踪已访问的节点     std::queue queue; // 创建一个队列，用于存储将要访问的节点      // 标记起始节点为已访问，并将其加入队列     visited[startVertex] = true;     queue.push(startVertex);      while (!queue.empty()) {         // 从队列中取出一个节点，并访问它         int currentVertex = queue.front();         queue.pop();         std::cout << "Visited " << currentVertex << std::endl;          // 遍历当前节点的所有邻居         for (int neighbor : graph[currentVertex]) {             if (!visited[neighbor]) { // 如果邻居没有被访问过                 visited[neighbor] = true; // 标记邻居为已访问                 queue.push(neighbor); // 将邻居节点加入队列中             }         }     } }  int main() {     // 使用邻接表表示图，图中包含6个节点（编号从0到5）     std::vector> graph = {         {1, 2},    // 节点0与节点1和节点2相连         {0, 3, 4}, // 节点1与节点0、节点3和节点4相连         {0, 4},    // 节点2与节点0和节点4相连         {1, 5},    // 节点3与节点1和节点5相连         {1, 2},    // 节点4与节点1和节点2相连         {3}        // 节点5与节点3相连     };      // 从节点0开始进行BFS遍历     std::cout << "BFS traversal starting from vertex 0:" << std::endl;     BFS(0, graph);      return 0; } 

在这段代码中，我们首先定义了一个BFS函数，它接受一个起始顶点和一个图表示作为输入。图是通过邻接表的形式表示的，其中graph是一个向量的向量，graph[i]包含与节点i相邻的所有节点。我们还定义了一个visited向量来跟踪已经访问过的节点，以避免重复访问。

我们将起始节点标记为已访问并将其加入到队列中。然后，我们进入一个循环，循环将一直运行直到队列为空。在循环的每一步，我们从队列中取出一个节点，输出它被访问的信息，并遍历所有邻居。如果邻居节点尚未被访问，我们就标记它为已访问，并将其加入队列。

当队列为空时，意味着从起始节点可达的所有节点都已被访问过，BFS遍历就完成了。在main函数中，我们定义了一个简单的图并调用了BFS函数来显示从节点0开始的BFS遍历结果。

这个简单的例子展示了BFS算法的基本原理和实现，但在实际应用中，可能需要根据特定问题对算法进行调整和优化。