17370845950

std::queue 是 C++ 中实现 BFS 最常用方式，需配合访问标记数组避免重复入队，且标记必须在入队时设置；图可用邻接表或邻接矩阵表示，稀疏图推荐邻接表。

用 std::queue 实现标准 BFS 遍历

广度优先搜索在 C++ 中最常用、最直观的实现方式是借助 std::queue，配合访问标记数组（或 std::set/std::unordered_set）避免重复入队。核心逻辑是：从起点入队 → 循环取队首 → 访问所有未访问邻接点并入队。

关键点：

• std::queue 是 FIFO 容器适配器，不支持随机访问或遍历，但完全满足 BFS 层序需求
• 图可用邻接表（vector>）或邻接矩阵（vector>）表示；稀疏图强烈推荐邻接表
• 访问标记必须在入队时设置（而非出队时），否则同一节点可能被多次加入队列

vector> graph = {{1,2}, {0,3}, {0,3}, {1,2}};
vector visited(graph.size(), false);
queue q;
q.push(0);
visited[0] = true;

while (!q.empty()) {
    int u = q.front(); q.pop();
    cout << u << " ";
    for (int v : graph[u]) {
        if (!visited[v]) {
            vi
sited[v] = true;
            q.push(v);
        }
    }
}

处理带权图或需要记录距离时用 pair 或结构体

纯 BFS 仅适用于无权图或所有边权相等的情形。若需在 BFS 过程中同步维护节点距离（如求最短路径长度），常见做法是把 node 和 dist 绑定为 pair 入队。

注意：

• 不要用 queue 配合外部数组“延迟更新”距离——这会导致距离值与实际出队顺序错位
• 如果边权不全为 1（比如有权重为 2 的边），BFS 不再适用，应改用 Dijkstra 算法
• 若图含负权边，Dijkstra 也不适用，需考虑 Bellman-Ford 或 SPFA

queue> q; // {node, dist}
q.push({0, 0});
vector dist(graph.size(), -1); // -1 表示未访问
dist[0] = 0;

while (!q.empty()) {
    auto [u, d] = q.front(); q.pop();
    for (int v : graph[u]) {
        if (dist[v] == -1) {
            dist[v] = d + 1;
            q.push({v, d + 1});
        }
    }
}

多源 BFS：多个起点同时入队

当问题要求“从任意一个起点出发的最短距离”（如矩阵中多个 '0' 扩散到 '1'），可将所有起点一次性压入队列，并初始化对应距离为 0。这本质上仍是标准 BFS，只是初始队列非单元素。

典型场景包括：

• 01 矩阵中每个位置到最近 0 的距离
• 腐烂橘子传播时间
• 双向 BFS 的前半部分初始化

陷阱：

• 误写成循环中逐个 push 再单独处理——这样会破坏层序性，必须所有起点先入队、再统一开始 while 循环
• 忘记对多个起点也做访问标记，导致重复入队

避免常见内存与逻辑错误

BFS 在 C++ 中容易因容器误用或边界疏忽引发崩溃或死循环：

• 图节点编号从 0 开始，但 graph.size() 可能小于最大节点 ID —— 若输入含孤立大编号点（如节点 100 但只有 5 条边），需用 max_node_id + 1 初始化 visited 或 dist
• queue::front() 和 queue::pop() 是两个独立操作，不能省略 pop()，否则无限循环
• 使用 vector> 存图时，确保每行都已 resize 或用 push_back 正确构建，空行会导致范围访问越界
• 在类成员函数中复用 queue 时，记得每次调用前 queue = queue() 清空（C++11 后可直接赋值空队列）

图论 BFS 看似简单，真正难的是根据题意准确建模——节点定义、边是否存在、是否允许回头、距离含义是否随层变化，这些细节一旦错，整个 BFS 就偏离目标。