蓝桥杯省赛冲刺（3）广度优先搜索

广度优先搜索（Breadth-First Search, BFS）是一种在图或树等非线性数据结构中遍历节点的算法，它从起始节点开始，按层级逐步向外扩展，即先访问离起始节点最近的节点，再访问这些节点的邻居，然后是邻居的邻居，以此类推。BFS利用队列数据结构来实现这种层级顺序的遍历。以下是广度优先搜索的C语言实现及应用的详细介绍：

### **算法描述**

广度优先搜索遵循以下基本步骤：

1. **初始化**：定义一个标志数组（通常为布尔数组）来记录每个节点是否已被访问。对于无向图，初始化所有节点为未访问状态。

2. **选择起始节点**：从图中选择一个起始节点作为搜索起点。通常在无指定起点时，可以选择任意未访问节点作为起始点。

3. **访问节点**：标记当前节点为已访问，并执行与节点相关操作（如输出节点信息、计算节点属性等）。

4. **入队邻居**：将当前节点的所有未访问邻居节点加入队列。队列确保了节点按照层次顺序被访问。

5. **出队节点**：从队列中取出下一个节点（即最先进入队列的节点，也就是距离起始节点最近且未访问过的节点）。重复步骤3-4，直到队列为空，表示所有与起始节点可达的节点已被访问。

### **C语言实现**

下面是一个使用C语言实现广度优先搜索算法的示例，以遍历一个无向图（用邻接矩阵表示）为例：

```c

#include <stdio.h>

#include <stdbool.h>

#include <queue>

// 定义图的最大顶点数和边的关系类型

#define MAX_VERTEX_NUM 10

typedef int VRType;

// 定义图的邻接矩阵表示

VRType graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

// 定义一个标志数组，记录节点是否已被访问

bool visited[MAX_VERTEX_NUM] = {false};

// 使用std::queue来存储待访问节点

std::queue<int> nodeQueue;

// 广度优先搜索函数

void bfs(int start_vertex) {

   // 标记起始节点为已访问，并将其加入队列

   visited[start_vertex] = true;

   nodeQueue.push(start_vertex);

   while (!nodeQueue.empty()) {

       // 取出队列头部的节点（距离起始节点最近且未访问过的节点）

       int current_vertex = nodeQueue.front();

       nodeQueue.pop();

       printf("Visited node: %d\n", current_vertex); // 输出节点信息

       // 遍历当前节点的所有邻居

       for (int i = 0; i < MAX_VERTEX_NUM; i++) {

           // 如果邻居节点未被访问且与当前节点存在连接

           if (!visited[i] && graph[current_vertex][i] != 0) {

               // 标记邻居节点为已访问，并将其加入队列

               visited[i] = true;

               nodeQueue.push(i);

           }

       }

   }

}

int main() {

   // 假设已填充了图的邻接矩阵graph

   // 选择一个起始节点，这里以节点0为例

   bfs(0);

   return 0;

}

```

在这个示例中，`bfs()` 函数接受起始节点编号作为参数，初始化队列并开始搜索过程。主函数 `main()` 调用 `bfs()` 以节点0为起始点启动搜索。

### **应用场景**

广度优先搜索在多个领域有广泛应用，包括但不限于：

- **图的连通性检测**：判断图中是否存在从一个节点到另一个节点的路径，同时可以确定两节点之间的最短路径（在所有边权重相等的情况下）。

- **社交网络中的朋友推荐**：查找与用户最近的人脉关系。

- **网络路由**：在网络中寻找最短路径（例如，IP路由表的构建）。

- **游戏AI**：在有限的行动空间内寻找最优或近似最优路径（如棋类游戏、迷宫求解等）。

- **网页抓取**：用于构建网站的目录结构或抓取特定深度的网页。

总之，广度优先搜索以其层级遍历的特性，适用于需要快速找到离起点最近节点及其路径，或解决最短路径问题（在边权相同的情况下）的情况。在C语言中，借助标准库提供的队列数据结构，可以方便地实现BFS算法。