BFS通过队列实现逐层遍历，先访问起始节点并标记，再将其未访问的邻接节点入队，重复直至队列为空；示例代码展示了无向图和网格中最短路径的应用，适用于最短路径、连通分量、状态搜索等问题。
广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索图或树的算法。它从起始节点开始，逐层访问其邻居节点，直到找到目标节点或遍历完整个图。C++ 中实现 BFS 通常借助队列（queue）结构来保证先进先出的访问顺序。
基本思路与实现步骤
BFS 的核心思想是：从源点出发，先访问所有直接相邻的节点，再依次访问这些相邻节点的未访问邻居，依此类推，像水波一样层层扩散。
实现流程如下：
使用一个队列存储待访问的节点 使用一个布尔数组或集合记录已访问的节点，防止重复访问 将起始节点入队，并标记为已访问 当队列非空时，取出队首节点，访问其所有未访问的邻接节点并入队 重复上述过程直到队列为空// 示例：用邻接表表示无向图的 BFS 实现
#include #include #include using namespace std;void bfs(const vector<vector>& adj, int start) { int n = adj.size(); vector visited(n, false); queue q; q.push(start); visited[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); cout << u << " "; // 输出当前访问的节点 for (int v : adj[u]) { if (!visited[v]) { visited[v] = true; q.push(v); } } }}int main() { // 构建一个简单的无向图：0-1, 0-2, 1-3, 2-4 vector<vector> adj(5); adj[0] = {1, 2}; adj[1] = {0, 3}; adj[2] = {0, 4}; adj[3] = {1}; adj[4] = {2}; cout << "BFS 遍历结果: "; bfs(adj, 0); // 从节点 0 开始遍历 cout << endl; return 0;}
在网格中的 BFS 应用
BFS 常用于二维网格问题，比如迷宫最短路径、图像填充、岛屿问题等。此时节点是坐标 (x, y)，邻居是上下左右四个方向。
立即学习“C++免费学习笔记（深入）”；
示例：在 0-1 网格中求从左上角到右下角的最短路径（只能走 0）。
#include #include #include using namespace std;int shortestPathBinaryMatrix(vector<vector>& grid) { if (grid[0][0] == 1) return -1; int n = grid.size(); vector<vector> visited(n, vector(n, false)); queue<vector> q; q.push({0, 0, 1}); // {x, y, distance} visited[0][0] = true; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; while (!q.empty()) { auto cell = q.front(); q.pop(); int x = cell[0], y = cell[1], dist = cell[2]; if (x == n-1 && y == n-1) return dist; for (int i = 0; i = 0 && nx = 0 && ny < n && !visited[nx][ny] && grid[nx][ny] == 0) { visited[nx][ny] = true; q.push({nx, ny, dist + 1}); } } } return -1; // 无法到达终点}
BFS 的典型应用场景
BFS 不仅用于图遍历，还在多种实际问题中有广泛应用：
最短路径问题：在无权图或网格中，BFS 能找到起点到终点的最少边数路径 连通分量检测：通过多次 BFS 可找出图中所有连通块 拓扑排序辅助：结合入度的 BFS 可实现 Kahn 算法 状态空间搜索：如八数码问题、单词接龙等，每个状态是一个节点 二叉树层序遍历：本质就是 BFS，按层输出节点值
基本上就这些。BFS 实现不复杂但容易忽略细节，比如访问标记的时机、边界判断、初始条件等。掌握好队列和状态管理，就能灵活应对各种变体问题。
以上就是c++++怎么实现广度优先搜索（BFS）_c++中BFS算法的实现与应用场景的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1481610.html
微信扫一扫 
支付宝扫一扫 
