BFS 是另一种基础搜索算法，在图论和搜索中有着广泛的应用。
一、BFS 本质
BFS = 广度优先搜索 = 层层扩展，像水波扩散。
核心数据结构：队列（queue）
queue<int> q;
q.push(start);
vis[start] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : 邻接的节点) {
if (!vis[v]) {
vis[v] = 1;
dis[v] = dis[u] + 1;
q.push(v);
}
}
}二、BFS 的典型应用
- 无权图的最短路径（边权为 1）
- 迷宫问题
- 求连通块
- 树的层次遍历
- 多源 BFS
三、0-1 BFS（双端队列 BFS）
用于边权只有 0 或 1 的图：
- 遇到权为 0 的边 → 从队首插入
- 遇到权为 1 的边 → 从队尾插入
- 本质上是 Dijkstra 的特化版本
四、双向 BFS
从起点和终点同时 BFS，在中间相遇。复杂度从 O(b^d) 降至 O(b^(d/2))。
五、A* 算法
结合 BFS 和贪心策略，使用启发式函数估计到目标的距离：
- 优先级 = 已走距离 + 估计剩余距离
- 当估计函数可纳（admissible）时，保证最优解
六、BFS 技巧总结
- 状态压缩：用整数/字符串表示状态
- vis 数组设计：根据状态空间选择合适的标记方式
- 剪枝：提前排除不可行的状态
推荐练习：
- 洛谷 P1443 马的遍历（基础 BFS）
- 洛谷 P1141 01迷宫
- 洛谷 P1602 字串变换（双向 BFS）
- 洛谷 P1379 八数码难题（A*）
暂无评论，快来抢沙发吧~ 🛋️