C++实现图的BFS算法详解

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

广度优先搜索（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保证按层次顺序访问节点，同时用布尔数组记录访问状态，防止重复访问。

基本流程如下：

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

示例代码：

#include 
#include 
#include 
using namespace std;

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

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

    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的完整程序：

#include 
#include 
#include 
using namespace std;

int main() {
    int n = 5;  // 5个顶点
    vector> graph(n + 1);

    // 添加边
    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 traversal: ";
    bfs(graph, 1, n);
    return 0;
}

输出结果为：1 2 3 4 5，体现了逐层遍历的特点。

应用场景与注意事项

BFS常用于求解无权图的最短路径、连通分量、拓扑排序等问题。注意以下几点：

• 确保图的顶点编号与数组大小匹配
• 有向图只需单向添加边
• 若图不连通，需对每个未访问节点调用BFS以遍历全部连通块
• 队列操作时间复杂度为O(V + E)，空间复杂度为O(V)