c++中如何实现图的广度优先遍历_c++图BFS遍历方法-C++-PHP中文网

c++中如何实现图的广度优先遍历_c++图BFS遍历方法

尼克

发布： 2025-10-07 21:31:01

原创

191人浏览过

答案：C++中BFS通过队列实现逐层遍历，使用邻接表存储图并用visited数组标记节点，从起始点入队开始，循环出队并访问其未标记的邻接点，直至队列为空，确保每个节点仅处理一次，时间复杂度为O(V+E)。

c++中如何实现图的广度优先遍历_c++图bfs遍历方法

在C++中实现图的广度优先遍历（BFS），核心是使用队列结构来逐层访问图中的节点。BFS适用于无向图或有向图，常用于寻找最短路径、连通性判断等场景。

图的存储方式：邻接表

通常用邻接表表示图，便于遍历每个节点的邻居。可以使用vector<vector<int>>来实现。

例如，graph[u] 存储所有与节点 u 相连的节点。

实现步骤说明

BFS的关键在于从起始节点出发，逐层扩展，避免重复访问。需要一个队列和一个标记数组。

职优简历

一款专注于互联网从业者的免费简历制作工具

233

查看详情

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

创建一个布尔数组 visited，记录节点是否被访问过
使用 queue<int> 存储待访问的节点
将起始节点入队，并标记为已访问
当队列不为空时，取出队首节点，访问其所有未访问的邻接点并入队

代码示例

以下是一个完整的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);
            }
        }
    }
}

int main() {
    int n = 5;
    vector<vector<int>> graph(n);

    // 构建无向图：0-1, 0-2, 1-3, 2-4
    graph[0] = {1, 2};
    graph[1] = {0, 3};
    graph[2] = {0, 4};
    graph[3] = {1};
    graph[4] = {2};

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

    return 0;
}

登录后复制