一、上期回顾完成七大算法综合刷题自测基础算法体系全部落地掌握。今天学习BFS 广度优先搜索和 DFS 回溯对应主打逐层向外遍历擅长求无权图最短路径。二、BFS 核心原理遍历规则由近到远、一层一层扩散底层依托队列 queue先进先出特性核心优势第一次抵达目标点即为最短路径适用场景迷宫寻路、二叉树层序遍历、岛屿统计、无权图最短路三、BFS 通用解题步骤初始化队列起点入队标记已访问队列不为空逐层取出队首元素遍历当前元素所有相邻合法节点未访问则标记入队循环直到队列为空四、基础模板框架#include iostream #include queue #include vector using namespace std; // 方向数组上下左右 int dx[] {-1,1,0,0}; int dy[] {0,0,-1,1}; void bfs() { queue节点类型 q; 起点入队; 标记访问; while(!q.empty()) { auto cur q.front(); q.pop(); 遍历四个方向 { 坐标越界判断 未访问且合法 标记访问 新节点入队 } } }五、例题 1二叉树层序遍历struct TreeNode { int val; TreeNode *left, *right; TreeNode(int x):val(x),left(nullptr),right(nullptr){} }; #include vector vectorvectorint levelOrder(TreeNode* root) { vectorvectorint res; if(!root) return res; queueTreeNode* q; q.push(root); while(!q.empty()) { int size q.size(); vectorint layer; for(int i0;isize;i) { TreeNode* cur q.front(); q.pop(); layer.push_back(cur-val); if(cur-left) q.push(cur-left); if(cur-right) q.push(cur-right); } res.push_back(layer); } return res; }六、例题 2迷宫最短路径二维网格从起点走到终点只能上下左右移动求最少步数int m,n; int grid[105][105]; bool vis[105][105]; int dx[]{-1,1,0,0}; int dy[]{0,0,-1,1}; struct Node { int x,y,step; }; int bfs(int sx,int sy,int ex,int ey) { queueNode q; q.push({sx,sy,0}); vis[sx][sy] true; while(!q.empty()) { Node cur q.front(); q.pop(); // 到达终点返回步数 if(cur.x ex cur.y ey) return cur.step; for(int i0;i4;i) { int nx cur.x dx[i]; int ny cur.y dy[i]; // 边界障碍访问判断 if(nx0nxmny0nyn!vis[nx][ny]grid[nx][ny]0) { vis[nx][ny] true; q.push({nx,ny,cur.step1}); } } } return -1; }七、BFS 与 DFS 核心区别BFS队列、逐层遍历、天然最短路径、空间开销偏大DFS递归 / 栈、一路深入、适合枚举所有方案、易栈溢出八、今日核心总结BFS 依靠队列实现层级遍历就近优先搜索方向数组统一处理上下左右移动代码复用性高首次触达目标即为最短路径求步数首选 BFS必须设置访问标记避免重复遍历死循环常用场景层序遍历、迷宫、岛屿、无权最短路九、课后练习手写二叉树层序遍历 BFS 代码简单迷宫模型计算起点到终点最短步数
