广度优先搜索（Breadth-First Search，BFS）是一种图遍历算法，通常用于搜索或遍历树和图等数据结构。其基本思想是先访问起始顶点，然后逐层遍历其相邻的顶点，直到找到目标顶点或遍历完所有顶点。
BFS通常使用队列作为辅助数据结构，通过先进先出的方式进行遍历。具体步骤如下：
- 将起始顶点放入队列中。
- 从队列中弹出一个顶点，并访问该顶点。
- 将该顶点的所有未访问过的相邻顶点放入队列。
- 重复步骤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 <iostream>
#include <list>
using namespace std;
class Graph {
int numVertices;
list<int>* 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<int>[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<int> queue;
visited[startVertex] = true;
queue.push_back(startVertex);
list<int>::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、在最小生成树中
