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});

BFS 常见错误和边界注意点

真正卡住人的往往不是算法逻辑，而是几个具体细节：空图、重复入队、越界、状态表示歧义。

GentleAI

GentleAI是一个高效的AI工作平台，为普通人提供智能计算、简单易用的界面和专业技术支持。让人工智能服务每一个人。

下载

立即学习“C++免费学习笔记（深入）”；

• 图为空或起点不可达时，确保有明确返回值（如 -1 或 nullptr），别让循环无限跑
• 邻接点检查必须在入队前做——否则同一节点可能被多次压入队列，爆炸性增长
• 二维坐标 BFS 务必检查 x,y 是否在 [0, row) 和 [0, col) 内，别只判正数
• 多源 BFS（如多个起点同时开始）只需初始把所有起点一起 push 并标记，其余逻辑完全一样
• 如果状态含时间、步数等维度，把它作为结构体一部分入队，不要试图靠外部变量同步

最易忽略的是：BFS 的“最短路径”性质仅在边权为 1 时成立。一旦有权重，就得换 Dijkstra 或 0-1 BFS ——这时候还硬套 queue 就错了。