c++怎么实现广度优先搜索（BFS）_c++中BFS算法的实现与应用场景-C++-PHP中文网

c++怎么实现广度优先搜索（BFS）_c++中BFS算法的实现与应用场景

穿越時空

发布： 2025-10-30 13:06:02

原创

908人浏览过

BFS通过队列实现逐层遍历，先访问起始节点并标记，再将其未访问的邻接节点入队，重复直至队列为空；示例代码展示了无向图和网格中最短路径的应用，适用于最短路径、连通分量、状态搜索等问题。

c++怎么实现广度优先搜索（bfs）_c++中bfs算法的实现与应用场景

广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索图或树的算法。它从起始节点开始，逐层访问其邻居节点，直到找到目标节点或遍历完整个图。C++ 中实现 BFS 通常借助队列（queue）结构来保证先进先出的访问顺序。

基本思路与实现步骤

BFS 的核心思想是：从源点出发，先访问所有直接相邻的节点，再依次访问这些相邻节点的未访问邻居，依此类推，像水波一样层层扩散。

实现流程如下：

使用一个队列存储待访问的节点
使用一个布尔数组或集合记录已访问的节点，防止重复访问
将起始节点入队，并标记为已访问
当队列非空时，取出队首节点，访问其所有未访问的邻接节点并入队
重复上述过程直到队列为空

// 示例：用邻接表表示无向图的 BFS 实现

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfs(const vector<vector<int>>& adj, int start) {
    int n = adj.size();
    vector<bool> visited(n, false);
    queue<int> 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<int>> 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 <iostream>
#include <vector>
#include <queue>
using namespace std;

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    if (grid[0][0] == 1) return -1;
    int n = grid.size();
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    queue<vector<int>> 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 < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n 
                && !visited[nx][ny] && grid[nx][ny] == 0) {
                visited[nx][ny] = true;
                q.push({nx, ny, dist + 1});
            }
        }
    }
    return -1;  // 无法到达终点
}

登录后复制