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

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

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

2025-11-22

浏览次数：次

返回列表

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

c++如何实现广度优先搜索(bfs)_c++图论算法中bfs的队列实现

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

基本思路

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

关键步骤：

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

图的表示方式

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

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

CA.LA

第一款时尚产品在线设计平台，服装设计系统

查看详情

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

BFS核心代码实现

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

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

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

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

const int MAXN = 7;
vector<int> 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<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() {
    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的核心在于队列的使用和访问状态的维护，结构清晰，适合解决分层遍历问题。

以上就是C++如何实现广度优先搜索(BFS)_C++图论算法中BFS的队列实现的详细内容，更多请关注其它相关文章！

# ai # 游戏开发 # 如何用 # 最短 # 适用于 # 图论 # 为空 # 如何实现 # stream # ios # c++ # edge # 遍历 # 烟台哪家网站推广好用 # 全网营销推广收费低吗 # 杭州如何建设企业网站 # 建设大型网站推广方案 # 淄博医院网站建设费用 # 哈尔滨网站建设过程 # 早茶节营销推广活动 # 徐闻酒店网站建设开发 # 营销推广团队建设及管理 # 春季童装网站推广方案 # 相关文章 # 是一种