标准BFS遍历用std::queue实现：取队首节点，访问其未访问邻接点并入队；邻接表用std::vector节省空间，visited数组防重复入队。
用 std::queue 实现标准 BFS 遍历
核心就是维护一个先进先出的队列，每次取出队首节点，访问它所有未访问过的邻接点并入队。C++ 标准库的 std::queue 是最直接的选择，不需要手写队列结构。
关键点：
- 用
std::vector<:vector>></:vector>存邻接表，比邻接矩阵更省空间（尤其稀疏图） - 用
std::vector<bool></bool>记录访问状态，下标即节点编号，避免重复入队 - 入队前必须检查是否已访问，否则可能无限循环或结果错乱
示例片段（无向图）：
std::vector<std::vector<int>> graph = {{1,2}, {0,3}, {0,3}, {1,2}};
std::vector<bool> visited(graph.size(), false);
std::queue<int> q;
q.push(0);
visited[0] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
std::cout << u << " ";
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
处理带权图或需要路径还原的 BFS
BFS 本身不适用于带权图的最短路径（除非所有边权相等），但若图中边权均为 1，BFS 天然给出单源最短距离；若还需知道怎么走到的，就得额外记录父节点。
立即学习“C++免费学习笔记（深入）”；
常见做法：
- 加一个
std::vector<int> parent</int>，初始化为 -1，每次从u扩展到v时设parent[v] = u - 距离数组
dist可用std::vector<int></int>，初始填 -1 或INT_MAX，dist[source] = 0，之后dist[v] = dist[u] + 1 - 路径还原时从目标节点不断跳
parent，直到 -1，再逆序输出
遇到 “超时” 或 “内存爆炸” 怎么办
不是算法逻辑错，而是数据结构或边界没控住。典型诱因：
- 图节点数极大（比如 1e5），但用了二维邻接矩阵（
vector<vector>>(n, vector<int>(n))</int></vector>），直接 O(n²) 内存炸掉 → 改用邻接表 - 没判重就 push 进队列，导致同一节点反复入队（比如无向图中 u→v 后又 v→u），队列迅速膨胀 → 必须在 push 前查
visited[v] - 输入格式含自环或重边，虽不影响正确性，但会徒增遍历次数 → 可在建图时去重，或依赖
visited自然过滤
和 DFS 混用时容易踩的坑
BFS 和 DFS 共享同一张图、同一套 visited 数组时，顺序和结果会互相干扰。实际项目中常见错误：
- 先跑一遍 BFS 把
visited全设为 true，接着调 DFS 却发现“什么都没走” → 解决：每次搜索前重置visited，或用局部变量 - 误以为 BFS 能像 DFS 那样方便回溯（比如找所有路径），但 BFS 天然不保存路径分支 → 真要枚举所有路径，得用 DFS 或改造 BFS 存完整路径（空间代价高）
- 多源 BFS（如多个起点同时开始）忘记把所有起点一次性 push 到队列并标记 → 结果只从第一个起点展开
真正难的不是写对一次 BFS，而是清楚它在哪种图结构、哪种问题约束下依然可靠——比如节点编号不连续、图用字符串 ID 而非整数、或者需要实时中断搜索。这些场景下，队列元素类型和访问标记方式都得跟着变。
