1. 广度优先搜索BFS算法解析第一次接触广度优先搜索(BFS)是在解决迷宫问题时当时我尝试用递归深搜总是超时直到发现BFS这个一层层扫荡的算法才恍然大悟。作为图论中最基础的遍历算法之一BFS以其独特的层序遍历思想在最短路径、状态搜索等问题中展现出惊人的效率。BFS的核心在于广度优先——像水波扩散一样逐层探索。想象你站在迷宫的起点先探查所有一步能到达的位置再以这些位置为新的起点继续向外探索。这种策略保证了首次到达终点时走过的路径必然是最短的这是它相比深度优先搜索(DFS)的最大优势。在洛谷等编程竞赛平台中BFS常出现在以下场景网格地图中的最短路径如P1443 马的遍历状态空间搜索如P1135 奇怪的电梯连通块统计如P1451 求细胞数量树或图的层序遍历2. BFS算法原理与实现细节2.1 算法框架与核心组件一个标准的BFS实现包含三个关键要素队列(Queue)存储待访问节点保证先进先出的访问顺序访问标记(Visited)记录已处理节点避免重复访问距离记录(Distance)存储起点到各节点的最短距离可选// 典型BFS伪代码框架 void bfs(Node start) { queueNode q; q.push(start); visited[start] true; while (!q.empty()) { Node current q.front(); q.pop(); for (Node neighbor : getNeighbors(current)) { if (!visited[neighbor]) { visited[neighbor] true; distance[neighbor] distance[current] 1; q.push(neighbor); } } } }2.2 方向处理技巧在网格类问题中如洛谷P1443方向处理有几种常见方式// 四方向移动 int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; // 八方向移动国际象棋中的马步 int knight_dx[8] {2, 1, -1, -2, -2, -1, 1, 2}; int knight_dy[8] {1, 2, 2, 1, -1, -2, -2, -1};提示使用方向数组能大幅减少代码量避免大量重复的if-else判断2.3 复杂度分析BFS的时间复杂度为O(VE)其中V是顶点数如网格中的格子总数E是边数如网格中可移动的路径总数空间复杂度主要取决于队列最大长度最坏情况下也是O(V)。对于N×N的网格复杂度通常表示为O(N²)。3. 洛谷经典题型实战3.1 P1443 马的遍历这道题要求计算国际象棋马到达棋盘每个点的最少步数是典型的BFS应用。关键点在于马走日字的八方向移动需要处理无法到达的点输出-1注意棋盘坐标系的转换#include iostream #include queue #include cstring using namespace std; struct Point { int x, y; }; const int dx[8] {2,1,-1,-2,-2,-1,1,2}; const int dy[8] {1,2,2,1,-1,-2,-2,-1}; int main() { int n, m, sx, sy; cin n m sx sy; int dist[n1][m1]; memset(dist, -1, sizeof(dist)); queuePoint q; q.push({sx, sy}); dist[sx][sy] 0; while (!q.empty()) { Point p q.front(); q.pop(); for (int i0; i8; i) { int nx p.x dx[i]; int ny p.y dy[i]; if (nx1 nxn ny1 nym dist[nx][ny]-1) { dist[nx][ny] dist[p.x][p.y] 1; q.push({nx, ny}); } } } for (int i1; in; i) { for (int j1; jm; j) { printf(%-5d, dist[i][j]); } printf(\n); } return 0; }3.2 P1135 奇怪的电梯这道题可以建模为状态空间搜索问题每个楼层是一个节点电梯按钮对应状态转移求从A到B的最少按键次数#include iostream #include queue using namespace std; int main() { int N, A, B; cin N A B; int k[N1]; for (int i1; iN; i) cin k[i]; queuepairint,int q; // {当前楼层, 步数} bool visited[N1] {false}; q.push({A, 0}); visited[A] true; while (!q.empty()) { auto [floor, steps] q.front(); q.pop(); if (floor B) { cout steps; return 0; } int up floor k[floor]; if (up N !visited[up]) { visited[up] true; q.push({up, steps1}); } int down floor - k[floor]; if (down 1 !visited[down]) { visited[down] true; q.push({down, steps1}); } } cout -1; return 0; }4. BFS优化技巧与常见错误4.1 双向BFS优化当起点和终点都明确时可以采用双向BFS大幅减少搜索空间。基本思路同时从起点和终点开始BFS当两个搜索相遇时立即终止总步数为两边步数之和// 双向BFS框架示例 int bidirectionalBFS(Node start, Node end) { queueNode q1, q2; unordered_mapNode, int vis1, vis2; q1.push(start); vis1[start] 0; q2.push(end); vis2[end] 0; while (!q1.empty() !q2.empty()) { // 从起点出发的BFS int size q1.size(); while (size--) { Node curr q1.front(); q1.pop(); if (vis2.count(curr)) return vis1[curr] vis2[curr]; // 处理邻居节点... } // 从终点出发的BFS size q2.size(); while (size--) { Node curr q2.front(); q2.pop(); if (vis1.count(curr)) return vis1[curr] vis2[curr]; // 处理邻居节点... } } return -1; // 无解 }4.2 常见错误与调试技巧队列溢出忘记pop或者错误处理队列导致无限循环解决方法在循环开始打印队列大小监控访问标记遗漏在将节点加入队列后忘记标记为已访问正确做法在q.push()后立即设置visited边界条件错误网格问题中未检查数组越界防御性编程先检查边界再访问数组多起点BFS处理不当需要将所有起点先加入队列典型应用多源最短路径问题调试技巧在BFS每层结束时打印当前层数和队列内容可视化搜索过程5. BFS的变种与应用扩展5.1 0-1BFS处理边权问题当图中边权只有0和1时可以使用双端队列优化边权为0添加到队列前端边权为1添加到队列后端// 0-1BFS示例处理边权0/1的最短路 void bfs01(Node start) { dequeNode q; int dist[MAX_N] {INF}; q.push_front(start); dist[start] 0; while (!q.empty()) { Node u q.front(); q.pop_front(); for (auto [v, w] : adj[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; if (w 1) q.push_back(v); else q.push_front(v); } } } }5.2 优先队列BFSDijkstra算法当边权为任意正数时BFS演变为Dijkstra算法使用优先队列保证每次处理当前距离最近的节点void dijkstra(Node start) { priority_queuepairint, Node pq; int dist[MAX_N] {INF}; pq.push({0, start}); dist[start] 0; while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (-d dist[u]) continue; // 重要优化 for (auto [v, w] : adj[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({-dist[v], v}); // 小根堆技巧 } } } }5.3 状态压缩BFS当需要记录额外状态时如携带钥匙、剩余步数等可以将状态编码后一起放入队列// 示例带有钥匙收集的最短路径 struct State { int x, y; int keys; // 位掩码表示钥匙收集情况 }; int bfsWithKeys(Node start) { queueState q; bool visited[MAX_X][MAX_Y][1K] {false}; q.push({start.x, start.y, 0}); visited[start.x][start.y][0] true; while (!q.empty()) { State s q.front(); q.pop(); if (isExit(s.x, s.y)) return s.steps; for (int i0; i4; i) { int nx s.x dx[i]; int ny s.y dy[i]; int nkeys s.keys; if (!isValid(nx, ny)) continue; // 处理钥匙和门的逻辑 if (isKey(nx, ny)) nkeys | (1 getKeyId(nx, ny)); if (isDoor(nx, ny) !(nkeys (1 getDoorKeyId(nx, ny)))) continue; if (!visited[nx][ny][nkeys]) { visited[nx][ny][nkeys] true; q.push({nx, ny, nkeys}); } } } return -1; }6. BFS在树结构中的应用虽然树是图的特例但BFS在树结构中仍有独特应用6.1 二叉树层序遍历vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; if (!root) return result; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); vectorint level; while (size--) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } result.push_back(level); } return result; }6.2 N叉树的最大深度int maxDepth(Node* root) { if (!root) return 0; queueNode* q; q.push(root); int depth 0; while (!q.empty()) { int size q.size(); depth; while (size--) { Node* node q.front(); q.pop(); for (Node* child : node-children) { if (child) q.push(child); } } } return depth; }6.3 二叉树最小深度与最大深度不同最小深度需要找到最近的叶子节点int minDepth(TreeNode* root) { if (!root) return 0; queuepairTreeNode*, int q; q.push({root, 1}); while (!q.empty()) { auto [node, depth] q.front(); q.pop(); if (!node-left !node-right) return depth; if (node-left) q.push({node-left, depth1}); if (node-right) q.push({node-right, depth1}); } return 0; }7. BFS在图论中的高级应用7.1 拓扑排序BFS是实现拓扑排序的经典算法Kahn算法vectorint topologicalSort(int numCourses, vectorvectorint prerequisites) { vectorvectorint graph(numCourses); vectorint inDegree(numCourses, 0); // 建图并计算入度 for (auto p : prerequisites) { graph[p[1]].push_back(p[0]); inDegree[p[0]]; } queueint q; // 所有入度为0的节点入队 for (int i0; inumCourses; i) { if (inDegree[i] 0) q.push(i); } vectorint result; while (!q.empty()) { int u q.front(); q.pop(); result.push_back(u); for (int v : graph[u]) { if (--inDegree[v] 0) { q.push(v); } } } if (result.size() ! numCourses) return {}; return result; }7.2 二分图检测使用BFS进行二分图染色检测bool isBipartite(vectorvectorint graph) { int n graph.size(); vectorint color(n, -1); for (int i0; in; i) { if (color[i] -1) { queueint q; q.push(i); color[i] 0; while (!q.empty()) { int u q.front(); q.pop(); for (int v : graph[u]) { if (color[v] -1) { color[v] color[u] ^ 1; q.push(v); } else if (color[v] color[u]) { return false; } } } } } return true; }7.3 多源最短路径当有多个起点时BFS可以高效计算每个点到最近起点的距离vectorvectorint multiSourceBFS(vectorpairint,int sources, int m, int n) { vectorvectorint dist(m, vectorint(n, -1)); queuepairint,int q; // 所有起点入队 for (auto [x,y] : sources) { dist[x][y] 0; q.push({x,y}); } int dx[4] {0,0,1,-1}; int dy[4] {1,-1,0,0}; while (!q.empty()) { auto [x,y] q.front(); q.pop(); for (int i0; i4; i) { int nx x dx[i]; int ny y dy[i]; if (nx0 nxm ny0 nyn dist[nx][ny]-1) { dist[nx][ny] dist[x][y] 1; q.push({nx,ny}); } } } return dist; }8. BFS在竞赛中的实战技巧8.1 状态表示优化当状态空间较大时需要优化状态表示使用位运算压缩状态如P2622 关灯问题哈希表存储已访问状态对称性剪枝如旋转、镜像等相同状态视为等价// 位压缩状态示例 int bfsWithBitmask(int startState) { queuepairint, int q; // {state, steps} unordered_setint visited; q.push({startState, 0}); visited.insert(startState); while (!q.empty()) { auto [state, steps] q.front(); q.pop(); if (isTarget(state)) return steps; for (int nextState : getNextStates(state)) { if (!visited.count(nextState)) { visited.insert(nextState); q.push({nextState, steps1}); } } } return -1; }8.2 双向BFS的洛谷实战以P1379 八数码难题为例双向BFS可以大幅提升效率int bidirectionalBFS(string start, string target) { queuestring q1, q2; unordered_mapstring, int vis1, vis2; q1.push(start); vis1[start] 0; q2.push(target); vis2[target] 0; while (!q1.empty() !q2.empty()) { // 正向搜索 int size q1.size(); while (size--) { string curr q1.front(); q1.pop(); if (vis2.count(curr)) return vis1[curr] vis2[curr]; int pos curr.find(0); int x pos / 3, y pos % 3; for (int i0; i4; i) { int nx x dx[i], ny y dy[i]; if (nx0 nx3 ny0 ny3) { string next curr; swap(next[pos], next[nx*3ny]); if (!vis1.count(next)) { vis1[next] vis1[curr] 1; q1.push(next); } } } } // 反向搜索 size q2.size(); while (size--) { string curr q2.front(); q2.pop(); if (vis1.count(curr)) return vis1[curr] vis2[curr]; // 类似正向的处理... } } return -1; }8.3 剪枝策略与优化有效剪枝能显著提升BFS效率可行性剪枝提前排除不可能达到目标的状态最优性剪枝当前路径已不如已知最优解时终止对称性剪枝识别并跳过等效状态启发式剪枝结合估价函数优先探索更有希望的分支// 带有估价函数的BFS类似A*算法 int bfsWithHeuristic(Node start) { auto heuristic [](Node a, Node b) { // 设计合适的估价函数 return abs(a.x - b.x) abs(a.y - b.y); }; priority_queuepairint, Node pq; unordered_mapNode, int dist; pq.push({-heuristic(start, target), start}); dist[start] 0; while (!pq.empty()) { auto [_, u] pq.top(); pq.pop(); if (u target) return dist[u]; for (auto [v, w] : getNeighbors(u)) { if (!dist.count(v) || dist[v] dist[u] w) { dist[v] dist[u] w; int priority -(dist[v] heuristic(v, target)); pq.push({priority, v}); } } } return -1; }9. BFS与其他算法的结合应用9.1 BFS与动态规划结合在某些问题中BFS可以用于动态规划的状态转移// 示例最短路径中的边权限制 int bfsWithDP(int start, int maxK) { // dist[i][k] 表示使用k次机会到达i的最短距离 vectorvectorint dist(n, vectorint(maxK1, INF)); queuepairint, int q; // {node, k} dist[start][0] 0; q.push({start, 0}); while (!q.empty()) { auto [u, k] q.front(); q.pop(); for (auto [v, w, isSpecial] : edges[u]) { if (isSpecial k maxK) { if (dist[v][k1] dist[u][k]) { dist[v][k1] dist[u][k]; q.push({v, k1}); } } if (dist[v][k] dist[u][k] w) { dist[v][k] dist[u][k] w; q.push({v, k}); } } } return *min_element(dist[target].begin(), dist[target].end()); }9.2 BFS与并查集结合在连通性问题中BFS可以辅助并查集进行区域划分// 示例岛屿数量问题 int numIslands(vectorvectorchar grid) { int m grid.size(), n grid[0].size(); int islands 0; for (int i0; im; i) { for (int j0; jn; j) { if (grid[i][j] 1) { islands; grid[i][j] 0; queuepairint,int q; q.push({i,j}); while (!q.empty()) { auto [x,y] q.front(); q.pop(); for (int d0; d4; d) { int nx x dx[d], ny y dy[d]; if (nx0 nxm ny0 nyn grid[nx][ny]1) { grid[nx][ny] 0; q.push({nx,ny}); } } } } } } return islands; }9.3 BFS与记忆化搜索对于某些状态转移问题可以结合记忆化提高效率// 示例单词接龙最短转换序列 int ladderLength(string beginWord, string endWord, vectorstring wordList) { unordered_setstring dict(wordList.begin(), wordList.end()); if (!dict.count(endWord)) return 0; queuepairstring,int q; q.push({beginWord, 1}); dict.erase(beginWord); while (!q.empty()) { auto [word, step] q.front(); q.pop(); if (word endWord) return step; // 生成所有可能的下一个单词 for (int i0; iword.size(); i) { char original word[i]; for (char ca; cz; c) { word[i] c; if (dict.count(word)) { q.push({word, step1}); dict.erase(word); // 相当于记忆化避免重复处理 } } word[i] original; } } return 0; }10. BFS在特殊场景下的应用10.1 隐式图的BFS遍历当图结构不是显式给出时BFS同样适用// 示例完美平方数问题 int numSquares(int n) { queuepairint,int q; // {剩余数值, 当前步数} vectorbool visited(n1, false); q.push({n, 0}); visited[n] true; while (!q.empty()) { auto [num, step] q.front(); q.pop(); if (num 0) return step; for (int i1; i*inum; i) { int next num - i*i; if (!visited[next]) { visited[next] true; q.push({next, step1}); } } } return n; // 最坏情况下全用1 }10.2 多维度状态BFS当状态需要多个维度描述时可以使用结构体或tuple// 示例带时间窗的最短路径 struct State { int position; int time; int tickets; // 剩余某种资源 }; int bfsWithMultiState(int start, int end, int maxTime, int maxTickets) { queueState q; vectorvectorvectorbool visited(n, vectorvectorbool(maxTime1, vectorbool(maxTickets1, false))); q.push({start, 0, maxTickets}); visited[start][0][maxTickets] true; while (!q.empty()) { State s q.front(); q.pop(); if (s.position end) return s.time; for (auto [next, cost, useTicket] : edges[s.position]) { // 正常通行的情况 if (s.time cost maxTime !visited[next][s.timecost][s.tickets]) { visited[next][s.timecost][s.tickets] true; q.push({next, s.time cost, s.tickets}); } // 使用票的情况 if (useTicket s.tickets 0 s.time 1 maxTime !visited[next][s.time1][s.tickets-1]) { visited[next][s.time1][s.tickets-1] true; q.push({next, s.time 1, s.tickets - 1}); } } } return -1; }10.3 概率型BFS当状态转移带有概率时可以记录到达概率// 示例迷宫中的概率传播 double probabilityBFS(vectorvectorint maze, vectorpairint,int exits) { struct Node { int x, y; double prob; }; auto cmp [](const Node a, const Node b) { return a.prob b.prob; // 最大堆 }; priority_queueNode, vectorNode, decltype(cmp) q(cmp); vectorvectordouble prob(maze.size(), vectordouble(maze[0].size(), 0.0)); prob[start.x][start.y] 1.0; q.push({start.x, start.y, 1.0}); while (!q.empty()) { Node curr q.top(); q.pop(); if (curr.prob prob[curr.x][curr.y]) continue; // 已有更优解 for (int i0; i4; i) { int nx curr.x dx[i], ny curr.y dy[i]; if (isValid(nx, ny) maze[nx][ny] ! 1) { double newProb curr.prob * 0.25; // 假设四个方向均等概率 if (newProb prob[nx][ny]) { prob[nx][ny] newProb; q.push({nx, ny, newProb}); } } } } double res 0; for (auto [x,y] : exits) { res prob[x][y]; } return res; }