c++如何实现图的广度优先搜索(BFS)_c++ BFS算法实现与讲解-C++-PHP中文网

c++如何实现图的广度优先搜索(BFS)_c++ BFS算法实现与讲解

穿越時空

发布： 2025-11-12 16:44:02

原创

203人浏览过

图的广度优先搜索从起始顶点开始逐层遍历，使用队列和访问标记数组避免重复访问；C++中常用邻接表vector<vector<int>>结合queue实现，示例构建5个顶点的图并从0开始BFS，输出0 1 2 3 4；适用于最短路径、连通分量等场景，稀疏图推荐邻接表，可扩展parent数组记录路径。

c++如何实现图的广度优先搜索(bfs)_c++ bfs算法实现与讲解

图的广度优先搜索（BFS）是一种用于遍历或搜索图的算法，它从起始顶点开始，逐层访问其邻接节点，使用队列保证访问顺序。在C++中，可以通过邻接表或邻接矩阵结合标准库queue来高效实现。

图的表示方式：邻接表

通常使用vector<vector<int>>表示邻接表，每个索引对应一个顶点，存储与其相连的顶点列表。

示例：

假设有5个顶点，边为 (0,1), (0,2), (1,3), (1,4)，邻接表构造如下：

vector<vector<int>> graph(5);
graph[0] = {1, 2};
graph[1] = {3, 4};
// 其他默认为空

登录后复制

BFS核心逻辑与实现步骤

BFS的关键是使用队列和访问标记数组，避免重复访问节点。

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

纳米搜索

纳米搜索：360推出的新一代AI搜索引擎

查看详情

步骤说明：

创建布尔数组visited记录每个顶点是否已访问
创建队列，将起始顶点入队并标记为已访问
当队列非空时，取出队首顶点并访问
将其所有未访问的邻接顶点入队并标记
循环直到队列为空

C++实现代码：

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

void bfs(const vector<vector<int>>& graph, int start) {
    int n = graph.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 : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

登录后复制

完整可运行示例

以下是一个完整的程序，构建图并执行BFS：

int main() {
    vector<vector<int>> graph(5);
    graph[0] = {1, 2};
    graph[1] = {0, 3, 4};
    graph[2] = {0};
    graph[3] = {1};
    graph[4] = {1};

    cout << "BFS traversal: ";
    bfs(graph, 0);
    return 0;
}

登录后复制

输出：
0 1 2 3 4