C++怎么实现图的广度优先搜索(BFS)_C++图算法与BFS实现方法

新闻中心 NEWS CENTER

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

C++怎么实现图的广度优先搜索(BFS)_C++图算法与BFS实现方法

2025-11-25

浏览次数：次

返回列表

广度优先搜索从起始节点开始逐层遍历，使用队列和访问标记数组实现，适用于求解最短路径、连通分量等问题，时间复杂度O(V+E)，空间复杂度O(V)。

c++怎么实现图的广度优先搜索(bfs)_c++图算法与bfs实现方法

广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索图的算法，它从起始顶点开始，逐层访问其邻接顶点，直到访问完所有可达顶点。在C++中，通常使用队列和访问标记数组来实现BFS。

图的表示方式

在C++中，图常用邻接表或邻接矩阵表示。对于稀疏图，邻接表更节省空间且效率更高。

使用vector>可以方便地实现邻接表：

// 假设n为顶点数
vector> graph(n + 1); // 若顶点从1开始编号
// 添加边 u -> v
graph[u].push_back(v);
graph[v].push_back(u); // 无向图需双向添加

BFS核心实现步骤

BFS借助queue保证按层次顺序访问节点，同时用布尔数组记录访问状态，防止重复访问。

基本流程如下：

美图云修

商业级AI影像处理工具

50 查看详情美图云修

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

示例代码：

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

void bfs(const vector<vector<int>>& graph, int start, int n) {
    vector<bool> visited(n + 1, false);
    queue<int> q;

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

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

        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

完整可运行示例

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

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

int main() {
    int n = 5;  <font color="#008000">// 5个顶点</font>
    vector<vector<int>> graph(n + 1);

    <font color="#008000">// 添加边</font>
    graph[1].push_back(2); graph[2].push_back(1);
    graph[1].push_back(3); graph[3].push_back(1);
    graph[2].push_back(4); graph[4].push_back(2);
    graph[3].push_back(5); graph[5].push_back(3);

    cout << "BFS tr*ersal: ";
    bfs(graph, 1, n);
    return 0;
}