C++如何实现图的广度优先搜索（BFS）？（代码示例）-C++-PHP中文网

C++中BFS使用队列按层遍历，以邻接表存储图，用visited数组防重访；对非连通图需遍历所有节点启动多次BFS；可扩展用于无权图最短路径、二分图判定等。

c++如何实现图的广度优先搜索（bfs）？（代码示例）

用C++实现图的广度优先搜索（BFS），核心是借助队列（queue）按层扩展访问节点，并用数组或集合标记已访问节点，避免重复入队。

使用邻接表存储图

邻接表适合稀疏图，用 vector> 表示：下标为起点，内部 vector 存所有邻接点。

例如：边 (0→1), (0→2), (1→3)，对应 graph[0] = {1,2}，graph[1] = {3}。

标准 BFS 实现（无权图，从起点开始遍历）

以下代码输出 BFS 遍历顺序（也可改造成求最短距离、连通分量等）：

Explainpaper

阅读学术论文的更好方法，你的学术论文阅读助手。

下载

立即学习“C++免费学习笔记（深入）”；

#include 
#include 
#include 
#include 

using namespace std;

void bfs(const vector>& graph, int start) {
    int n = graph.size();
    vector visited(n, false);
    queue q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";  // 访问当前节点

        // 遍历所有邻接点
        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    cout << endl;
}

// 示例用法
int main() {
    // 构建 4 个节点的有向图：0→1, 0→2, 1→3, 2→3
    vector> graph(4);
    graph[0] = {1, 2};
    graph[1] = {3};
    graph[2] = {3};
    // graph[3] 为空

    bfs(graph, 0); // 输出：0 1 2 3
    return 0;
}

扩展：支持无向图与多连通分量

若图不连通，需对每个未访问节点启动一次 BFS：

外层加循环遍历所有节点 i ∈ [0, n)
每次遇到 !visited[i] 就调用一次 BFS，可视为发现一个新连通分量
无向图建图时，边 u-v 要双向添加：graph[u].push_back(v); graph[v].push_back(u);

常见变体用途

单源最短路径（无权图）：用 vector dist(n, -1) 记录距离，起始点 dist[start] = 0，每次入队时设 dist[v] = dist[u] + 1
判断二分图：用颜色数组（如 0/1），BFS 过程中检查邻接点是否冲突
层序遍历控制：用额外变量记录当前层节点数（如先记 int levelSize = q.size()），每轮处理完一层再继续

基本上就这些。BFS 关键在于“先进先出”和“即时标记”，别漏判 visited 就不会死循环。