广度优先搜索（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）已经被访问过。我们参观它。
访问队列中最后剩余的项目以检查它是否有未访问的邻居
由于队列为空，我们就完成了图的广度优先遍历。
广度优先搜索伪代码
create a queue Q -- 创建队列Q
mark v as visited and put v into Q -- 将v标记为已访问，并将v放入Q中
while Q is non-empty -- 如果Q不为空
remove the head u of Q -- 移除Q的头u
mark and enqueue all (unvisited) neighbours of u -- 标记并排列u的所有（未访问的）邻居
广度优先搜索算法的代码及其示例如下所示。代码已被简化，以便我们可以专注于算法而不是其他细节。
// BFS algorithm in C
#include <stdio.h>
#include <stdlib.h>
#define SIZE 40
struct queue {
int items[SIZE];
int front;
int rear;
};
struct queue* createQueue();
void enqueue(struct queue* q, int);
int dequeue(struct queue* q);
void display(struct queue* q);
int isEmpty(struct queue* q);
void printQueue(struct queue* q);
struct node {
int vertex;
struct node* next;
};
struct node* createNode(int);
struct Graph {
int numVertices;
struct node** adjLists;
int* visited;
};
// BFS algorithm
void bfs(struct Graph* graph, int startVertex) {
struct queue* q = createQueue();
graph->visited[startVertex] = 1;
enqueue(q, startVertex);
while (!isEmpty(q)) {
printQueue(q);
int currentVertex = dequeue(q);
printf("Visited %d\n", currentVertex);
struct node* temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->vertex;
if (graph->visited[adjVertex] == 0) {
graph->visited[adjVertex] = 1;
enqueue(q, adjVertex);
}
temp = temp->next;
}
}
}
// Creating a node
struct node* createNode(int v) {
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Creating a graph
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct node*));
graph->visited = malloc(vertices * sizeof(int));
int i;
for (i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
// Add edge
void addEdge(struct Graph* graph, int src, int dest) {
// Add edge from src to dest
struct node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
// Add edge from dest to src
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
// Create a queue
struct queue* createQueue() {
struct queue* q = malloc(sizeof(struct queue));
q->front = -1;
q->rear = -1;
return q;
}
// Check if the queue is empty
int isEmpty(struct queue* q) {
if (q->rear == -1)
return 1;
else
return 0;
}
// Adding elements into queue
void enqueue(struct queue* q, int value) {
if (q->rear == SIZE - 1)
printf("\nQueue is Full!!");
else {
if (q->front == -1)
q->front = 0;
q->rear++;
q->items[q->rear] = value;
}
}
// Removing elements from queue
int dequeue(struct queue* q) {
int item;
if (isEmpty(q)) {
printf("Queue is empty");
item = -1;
} else {
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
printf("Resetting queue ");
q->front = q->rear = -1;
}
}
return item;
}
// Print the queue
void printQueue(struct queue* q) {
int i = q->front;
if (isEmpty(q)) {
printf("Queue is empty");
} else {
printf("\nQueue contains \n");
for (i = q->front; i < q->rear + 1; i++) {
printf("%d ", q->items[i]);
}
}
}
int main() {
struct Graph* graph = createGraph(6);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 1, 4);
addEdge(graph, 1, 3);
addEdge(graph, 2, 4);
addEdge(graph, 3, 4);
bfs(graph, 0);
return 0;
}
代码已被简化，以便我们可以专注于算法而不是其他细节。
BFS算法复杂度
BFS算法的时间复杂度用 的形式表示O(V + E)，其中V是节点数，E 是边数。该算法的空间复杂度为O(V)。
BFS算法应用
1、通过搜索索引建立索引
2、用于 GPS 导航
3、路径寻找算法
4、在 Ford-Fulkerson 算法中找到网络中的最大流量
5、无向图中的循环检测
6、在最小生成树中
