c++ 广度优先搜索（Breadth-First Search，BFS）

        广度优先搜索（Breadth-First Search，BFS）是一种图遍历算法，通常用于搜索或遍历树和图等数据结构。其基本思想是先访问起始顶点，然后逐层遍历其相邻的顶点，直到找到目标顶点或遍历完所有顶点。

BFS通常使用队列作为辅助数据结构，通过先进先出的方式进行遍历。具体步骤如下：

1. 将起始顶点放入队列中。
2. 从队列中弹出一个顶点，并访问该顶点。
3. 将该顶点的所有未访问过的相邻顶点放入队列。
4. 重复步骤2和3，直到队列为空或找到目标顶点为止。

        BFS算法保证在遍历过程中按层次访问顶点，可以用于查找最短路径、解决迷宫问题等。由于使用队列作为辅助数据结构，BFS的空间复杂度较高，但时间复杂度相对较低。

广度优先搜索示例
让我们通过一个例子来看看广度优先搜索算法是如何工作的。我们使用具有 5 个顶点的无向图。

具有 5 个顶点的无向图

我们从顶点 0 开始，BFS 算法首先将其放入 Visited 列表中，并将其所有相邻顶点放入堆栈中。 

访问起始顶点并将其相邻顶点添加到队列中

接下来，我们访问队列前面的元素（即 1）并访问其相邻节点。由于 0 已经被访问过，所以我们访问 2。

 访问起始节点0的第一个邻居，即1

顶点 2 在 4 中有一个未访问的相邻顶点，因此我们将其添加到队列的后面并访问位于队列前面的 3。

 访问之前添加到队列中的 2 以添加其邻居

4 仍在队列中

队列中只剩下 4 个节点，因为 3 的唯一相邻节点（即 0）已经被访问过。我们参观它。

 访问队列中最后剩余的项目以检查它是否有未访问的邻居

由于队列为空，我们就完成了图的广度优先遍历。 

示例代码：

// BFS algorithm in C++

#include
#include

using namespace std;

class Graph {
  int numVertices;
  list* adjLists;
  bool* visited;

   public:
  Graph(int vertices);
  void addEdge(int src, int dest);
  void BFS(int startVertex);
};

// Create a graph with given vertices,
// and maintain an adjacency list
Graph::Graph(int vertices) {
  numVertices = vertices;
  adjLists = new list[vertices];
}

// Add edges to the graph
void Graph::addEdge(int src, int dest) {
  adjLists[src].push_back(dest);
  adjLists[dest].push_back(src);
}

// BFS algorithm
void Graph::BFS(int startVertex) {
  visited = new bool[numVertices];
  for (int i = 0; i < numVertices; i++)
    visited[i] = false;

  list queue;

  visited[startVertex] = true;
  queue.push_back(startVertex);

  list::iterator i;

  while (!queue.empty()) {
    int currVertex = queue.front();
    cout << "Visited " << currVertex << " ";
    queue.pop_front();

    for (i = adjLists[currVertex].begin(); i != adjLists[currVertex].end(); ++i) {
      int adjVertex = *i;
      if (!visited[adjVertex]) {
        visited[adjVertex] = true;
        queue.push_back(adjVertex);
      }
    }
  }
}

int main() {
  Graph g(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 0);
  g.addEdge(2, 3);
  g.addEdge(3, 3);

  g.BFS(2);

  return 0;
}

代码已被简化，以便我们可以专注于算法而不是其他细节。

BFS算法复杂度
BFS算法的时间复杂度用 的形式表示O(V + E)，其中V是节点数，E 是边数。该算法的空间复杂度为O(V)。

BFS算法应用
1、通过搜索索引建立索引
2、用于 GPS 导航
3、路径寻找算法
4、在 Ford-Fulkerson 算法中找到网络中的最大流量
5、无向图中的循环检测
6、在最小生成树中