搜索算法 之 广度优先搜索（BFS, Breadth-First Search）

搜索算法 之 广度优先搜索（BFS, Breadth-First Search）

1. 基础概念

1.1 定义

广度优先搜索是一种逐层遍历节点的算法，首先访问距离起点最近的节点，再逐渐扩展到更远的节点。BFS使用队列作为辅助数据结构，将每个节点的邻居依次加入队列，直到所有节点被访问。

1.2 特点

• 利用队列先进先出的特性，逐层遍历图或树。
• 适用于查找最短路径和无权图的路径搜索。
• 算法过程是无递归的，逻辑较为清晰。

1.3 使用场景

• 寻找图中两点之间的最短路径。
• 解决连通性问题，例如岛屿数量。
• 层次遍历树结构，如树的层序遍历。

2. 实现与操作

2.1 核心操作实现

以下为使用 C 语言实现广度优先搜索的核心代码：

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_NODES 100 // 图结构的定义 typedef struct Graph { int adjMatrix[MAX_NODES][MAX_NODES]; // 邻接矩阵 int numNodes; // 节点数量 } Graph; // 初始化图 void initGraph(Graph *graph, int numNodes) { graph->numNodes = numNodes; for (int i = 0; i < numNodes; i++) { for (int j = 0; j < numNodes; j++) { graph->adjMatrix[i][j] = 0; } } } // 添加边 void addEdge(Graph *graph, int src, int dest) { graph->adjMatrix[src][dest] = 1; graph->adjMatrix[dest][src] = 1; // 无向图 } // 广度优先搜索 (BFS) void bfs(Graph *graph, int startNode) { bool visited[MAX_NODES] = {false}; int queue[MAX_NODES]; int front = 0, rear = 0; // 将起始节点标记为已访问并入队 visited[startNode] = true; queue[rear++] = startNode; printf("BFS traversal starting from node %d: ", startNode); while (front < rear) { int currentNode = queue[front++]; printf("%d ", currentNode); // 遍历邻居节点 for (int i = 0; i < graph->numNodes; i++) { if (graph->adjMatrix[currentNode][i] && !visited[i]) { visited[i] = true; queue[rear++] = i; } } } printf("\n"); } // 主函数 int main() { Graph graph; initGraph(&graph, 6); addEdge(&graph, 0, 1); addEdge(&graph, 0, 2); addEdge(&graph, 1, 3); addEdge(&graph, 1, 4); addEdge(&graph, 2, 5); bfs(&graph, 0); return 0; } </stdbool.h></stdlib.h></stdio.h>

2.2 代码详解

• Graph结构体存储邻接矩阵和节点数量。
• initGraph初始化图，清空邻接矩阵。
• addEdge添加无向边，使节点互相连接。
• bfs实现BFS算法，通过队列逐层遍历节点。
• 在main函数中创建示例图并调用bfs函数进行遍历。

3. 时间与空间复杂度分析

3.1 时间复杂度

对于一个图，BFS需要访问所有节点和所有边。时间复杂度为：O(V + E)，其中V为节点数，E为边数。

3.2 空间复杂度

BFS使用队列和访问数组，空间复杂度为O(V)。

4. 优缺点与局限性

4.1 优点

• 保证找到最短路径（在无权图中）。
• 实现简单，易于理解。

4.2 缺点与局限性

• 对大规模图需要较多内存。
• 无法处理加权图的最短路径问题。

5. 常见应用场景

BFS在图搜索、路径规划、连通性检测等问题中应用广泛。例如：

• 最短路径问题。
• 连通性检测。
• 图的层次遍历。

6. 代码编译与运行

6.1 编译命令

gcc bfs.c -o bfs && ./bfs

6.2 测试用例

运行示例中，输出如下：

BFS traversal starting from node 0: 0 1 2 3 4 5