C++如何实现广度优先搜索(BFS)_C++图论算法中BFS的队列实现

广度优先搜索（BFS）是一种按层遍历图的算法，使用队列实现并维护访问标记，适用于最短路径与连通性问题。从起始节点开始，依次将未访问的邻接节点入队，直至队列为空。C++中常用vector数组构建邻接表存储图结构，并通过bool数组记录节点访问状态。核心步骤包括：起始节点入队并标记、循环处理队首节点及其邻接点，直到队列为空。示例程序构建含6个节点的无向图，调用BFS后输出结果为1 2 3 4 5 6，体现了逐层扩展的遍历顺序。该算法结构清晰，关键在于队列调度与状态控制。

广度优先搜索（BFS）是图论中一种基础的遍历算法，适用于求解最短路径、连通性等问题。在C++中，BFS通常借助队列（queue）实现，保证按层访问节点。

基本思路

BFS从起始节点开始，先访问其所有邻接节点，再逐层向外扩展。使用一个队列保存待访问的节点，同时用一个数组或集合记录已访问的节点，避免重复处理。

关键步骤：

将起始节点入队，并标记为已访问
当队列非空时，取出队首节点
访问该节点的所有未访问邻接节点，依次入队并标记
重复直到队列为空

图的表示方式

常用邻接表存储图，C++中可用vector的数组或vector的vector实现。

示例：无向图的邻接表表示

const int MAXN = 1e5 + 5;
vector graph[MAXN];  // 邻接表
bool visited[MAXN];        // 访问标记数组

BFS核心代码实现

使用STL中的queue完成节点调度。

void bfs(int start) {
    queue 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遍历

构建一个包含6个节点的无向图并执行BFS。

#include 
#include 
#include 
using namespace std;

const int MAXN = 7;
vector graph[MAXN];
bool visited[MAXN];

void addEdge(int u, int v) {
    graph[u].push_back(v);
    graph[v].push_back(u);
}

void bfs(int start) {
    queue 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() {
    addEdge(1, 2);
    addEdge(1, 3);
    addEdge(2, 4);
    addEdge(2, 5);
    addEdge(3, 6);

    bfs(1);  // 输出: 1 2 3 4 5 6
    return 0;
}

基本上就这些。BFS的核心在于队列的使用和访问状态的维护，结构清晰，适合解决分层遍历问题。

# edge # ai # c++ # ios # stream # bool # 循环 # 算法 # 遍历 # 为空 # 适用于 # 最短 # 是一种 # 向外 # 关键在于 # 时用 # 性问题 # 连通性

返回目录在线咨询

上一篇：Python实现自动为照片添加日期并分类的方法
下一篇：移动优化对搜索引擎排名的重要性是什么_SEO优化教程

您的项目需求