应使用std::queue配合visited数组实现标准BFS：起点入队并标记，循环取队首、遍历未访问邻接点、入队前立即标记，需层数时用q.size()快照当前层宽度。
直接用 std::queue 配合 std::vector 或 std::unordered_set 管理访问状态，就能写出健壮、可读的 BFS；别手写队列，也别在未判重时反复入队。
怎么用 std::queue 写标准 BFS 框架
BFS 的核心是“一层层扩散”，std::queue 天然支持先进先出，适合模拟这个过程。关键不是循环次数，而是每次处理完当前层所有节点后再进下一层。
- 初始化：把起点入队，并标记为已访问（如写入
visited数组或集合） - 主循环：
while (!q.empty())，每次取队首，遍历其所有未访问邻接点 - 扩展逻辑：对每个合法邻接点，标记已访问并入队 —— 注意：必须在入队前/同时标记，否则同一节点可能被多次加入
- 若需层数信息（如最短距离），可在每层开始前用
q.size()快照当前层宽度，然后循环处理这若干个节点
std::queue<int> q;
std::vector<bool> visited(n, false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
图是邻接表还是邻接矩阵？影响什么
邻接表（vector<vector<int>>）更常用，空间省、遍历快；邻接矩阵（vector<vector<bool>>）适合点数少（O(n)。
- 邻接表：遍历
graph[u]即得所有邻居，平均O(degree(u)) - 邻接矩阵：需
for (int v = 0; v < n; ++v)全扫，再判断adj[u][v]，总复杂度O(n²) - 网格类题目（如二维数组上下左右移动）通常不建图，直接用坐标加四个方向偏移计算邻居，避免冗余存储
为什么常见 “超时” 或 “重复访问” 错误
根本原因几乎都是访问标记时机不对，或者压根没做标记。
立即学习“C++免费学习笔记（深入）”；
- 错误写法：
q.push(v); visited[v] = true;放在循环体末尾 —— 若多个节点同时指向v，v可能在入队前已被其他路径加入过，但此时还没标记，导致重复入队 - 正确顺序：检查
!visited[v]后，立刻设visited[v] = true，再q.push(v) - 漏判边界：比如网格中没检查
x < 0 || x >= rows，导致越界访问或无限循环 - 用
std::set或std::unordered_set做visited时，注意自定义结构体需提供hash或operator<，否则编译不过
需要返回路径或最短距离时怎么改
只靠队列不够，得额外记录“从哪来”或“走了几步”。不推荐在队列里塞复杂结构体，用辅助容器更清晰。
- 求最短距离：声明
vector<int> dist(n, -1)，起点设dist[start] = 0，每次更新邻居时dist[v] = dist[u] + 1 - 求路径：声明
vector<int> prev(n, -1)，每次设置prev[v] = u，结束后从终点倒推回起点 - 如果起点不唯一（如多源 BFS），初始就把所有起点入队并设对应
dist为 0，其余逻辑不变
真正容易卡住的地方，往往不是算法逻辑，而是标记位置错了一行、网格越界少判了一个方向、或者用 unordered_set 存 pair<int,int> 却忘了写哈希函数。
