c++中如何实现广度优先搜索BFS_c++ BFS算法模板_技术教程

用 queue 实现标准 BFS 遍历的核心是利用其 FIFO 特性逐层扩展，初始化起点入队并标记访问，循环中取队首、出队、遍历未访邻接点并入队标记；带层级信息时需记录每层大小并内嵌循环处理；非整数节点宜用 unordered_set 配自定义哈希；注意空图、重复入队、越界、多源初始化及边权为 1 的前提。

用 `queue` 实现标准 BFS 遍历

标准 BFS 的核心是“一层层扩散”，C++ 中直接用 std::queue 最自然。它保证先进先出，天然适配层级顺序。注意别误用 std::stack（那是 DFS），也别手写数组模拟队列——除非有极端性能要求且已确认瓶颈在此。

初始化时把起点 push 进队，并标记已访问（常用 vector 或 unordered_set）
循环条件是 !q.empty()，每次 q.front() 取出节点，q.pop() 移除
对当前节点所有未访问邻接点，标记 + 入队
图可用邻接表 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();
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}

带层级信息的 BFS（如求最短距离、按层处理）

很多题目不只要遍历，还要知道“当前在第几层”或“从起点到某点最少几步”。这时不能简单地每次取一个节点，而要一次处理完当前整层。

用 int level_size = q.size() 记录本层节点数，再套一层循环
每轮内完成 level_size 次 pop，期间新入队的节点属于下一层
每处理完一层，level++ 或存入结果数组
避免在循环中动态修改 q.size() 判断条件——那会出错

int steps = 0;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
int u = q.front(); q.pop();
if (u == target) return steps;
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
++steps;
}

处理非整数节点或复杂状态的 BFS

当节点不是简单编号（比如坐标 (x,y)、字符串状态、或带额外约束的元组），就不能用 vector 做访问标记了。

优先用 unordered_set 存状态，重载 hash 和 ==，或用 set（稍慢但省事）
坐标常用 pair，可直接用 make_pair(x,y)；C++20 起支持 std::hash，之前需自定义
字符串状态（如八数码、单词接龙）直接用 string 作 key，unordered_set 即可
避免把整个状态对象反复拷贝进队列——用 move 或存指针（谨慎生命周期）

// 坐标 BFS 示例（无 hash 版）
struct Point { int x, y; };
bool operator==(const Point& a, const Point& b) { return a.x == b.x && a.y == b.y; }
struct HashPoint { size_t operator()(const Point& p) const { return hash()(p.x * 1000000LL + p.y); } };
queue q;
unordered_set visited;
q.push({0,0});
visited.insert({0,0});