C++怎么实现广度优先搜索(BFS)_C++图的遍历与队列应用

广度优先搜索从起始节点开始逐层遍历，使用队列实现并用布尔数组标记访问状态，避免重复访问。示例代码展示了无向图的邻接表表示及BFS遍历过程，输出结果为0 1 2 3 4 5；通过记录队列大小可分层输出，应用于最短路径、连通性等问题，时间与空间复杂度均为O(V + E)。

广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索图或树的算法。它从起始节点开始，先访问其所有邻接节点，再逐层向外扩展，直到遍历完所有可达节点。BFS通常使用队列（queue）来实现，保证按层次顺序访问节点。

图的表示方式

在C++中，图常用邻接表表示，可以用vector>存储。例如，graph[u] 存储节点 u 所有直接连接的节点。

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

vector> graph = {
    {1, 2},      // 节点0连接1和2
    {0, 3, 4},   // 节点1连接0、3、4
    {0, 5},      // 节点2连接0、5
    {1},         // 节点3连接1
    {1},         // 节点4连接1
    {2}          // 节点5连接2
};

BFS基本实现步骤

BFS的核心是使用队列维护待访问节点，并用布尔数组记录已访问状态，避免重复访问。

实现要点：

• 使用queue保存待处理节点
• 使用vector标记是否访问过
• 从起点入队，循环出队并处理其邻居
• 未访问的邻居入队并标记

C++代码实现

#include 
#include 
#include 
using namespace std;

void bfs(const vector>& graph, int start) {
    int n = graph.size();
    vector visited(n, false);  // 标记访问状态
    queue q;

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

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";  // 输出当前节点

        // 遍历u的所有邻接节点
        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

// 示例调用
int main() {
    vector> graph = {{1,2}, {0,3,4}, {0,5}, {1}, {1}, {2}};
    cout << "BFS traversal: ";
    bfs(graph, 0);
    return 0;
}

输出结果：

0 1 2 3 4 5

带层级信息的BFS

有时需要知道每个节点所在的层次（距离起点的步数），可以在遍历时记录层数。

修改版：输出每层节点

void bfsWithLevel(const vector>& graph, int start) {
    int n = graph.size();
    vector visited(n, false);
    queue q;

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

    while (!q.empty()) {
        int size = q.size();  // 当前层的节点数
        cout << "Level " << level << ": ";

        while (size--) {
            int u = q.front();
            q.pop();
            cout << u << " ";

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

输出示例：

Level 0: 0 
Level 1: 1 2 
Level 2: 3 4 5 

应用场景与注意事项

BFS常用于求解最短路径（无权图）、连通分量、拓扑排序等问题。

常见用途：

• 计算两个节点间的最短路径（边权为1）
• 判断图是否连通
• 解决迷宫最短路径问题
• 社交网络中查找好友关系层数

注意点：

• 确保图不为空，起始节点有效
• 无向图需防止来回访问（靠visited数组控制）
• 有向图同样适用，只需按邻接表方向遍历
• 空间复杂度O(V + E)，时间复杂度O(V + E)

基本上就这些。掌握队列的使用和访问标记是关键。