广度优先搜索(BFS)
算法概述
【广度优先搜索】是一种图搜索算法，用于遍历或搜索图中的节点。它从起始节点开始，逐层向外扩展，直到找到目标节点或遍历完所有节点。BFS通常用于寻找最短路径、连通性等问题。
算法设计思路
广度优先搜索的核心思想是：使用队列来实现层次遍历，确保首先访问距离起点最近的节点，然后逐层向外扩展。其基本步骤如下：
- 将起始节点加入队列，并标记为已访问
- 当队列不为空时，重复以下步骤：
- 从队列中取出一个节点
- 访问该节点的所有未被访问的邻居节点，并将它们加入队列
- 直到找到目标节点或队列为空
代码实现与解析
基本BFS实现
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
// 广度优先搜索函数
void bfs(const vector<vector<int>>& graph, int start) {
queue<int> q; // 队列用于存储待访问的节点
unordered_set<int> visited; // 集合用于记录已访问的节点
q.push(start); // 将起始节点加入队列
visited.insert(start); // 标记起始节点为已访问
while (!q.empty()) {
int node = q.front(); // 取出队首节点
q.pop();
cout << "访问节点: " << node << endl;
// 访问所有邻居节点
for (int neighbor : graph[node]) {
if (visited.find(neighbor) == visited.end()) { // 如果邻居节点未被访问
q.push(neighbor); // 加入队列
visited.insert(neighbor); // 标记为已访问
}
}
}
}
int main() {
// 示例图的邻接表表示
vector<vector<int>> graph = {
{1, 2}, // 节点0的邻居
{0, 3, 4}, // 节点1的邻居
{0, 4}, // 节点2的邻居
{1, 5}, // 节点3的邻居
{1, 2, 5}, // 节点4的邻居
{3, 4} // 节点5的邻居
};
bfs(graph, 0); // 从节点0开始进行广度优先搜索
return 0;
}
时间复杂度分析
- 时间复杂度：O(V + E)，其中V是节点数，E是边数
- 空间复杂度：O(V)，需要存储队列和访问标记
优化策略
【双向BFS】当同时知道起点和终点时，可以从两端同时开始BFS，直到两个搜索相遇
bool bidirectionalBFS(int start, int end) { if (start == end) return true; queue<int> q1, q2; unordered_set<int> visited1, visited2; q1.push(start); q2.push(end); visited1.insert(start); visited2.insert(end); while (!q1.empty() && !q2.empty()) { // 总是从较小的队列扩展 if (q1.size() > q2.size()) { swap(q1, q2); swap(visited1, visited2); } int size = q1.size(); for (int i = 0; i < size; i++) { int node = q1.front(); q1.pop(); for (int neighbor : graph[node]) { if (visited1.count(neighbor)) continue; // 已访问 if (visited2.count(neighbor)) { return true; // 两个搜索相遇 } visited1.insert(neighbor); q1.push(neighbor); } } } return false; // 无法到达 }【01BFS】处理边权为0或1的最短路径问题时，可以用双端队列优化
vector<int> bfs01(vector<vector<pair<int, int>>>& graph, int start) { int n = graph.size(); vector<int> dist(n, INT_MAX); deque<int> dq; // 使用双端队列 dist[start] = 0; dq.push_front(start); while (!dq.empty()) { int node = dq.front(); dq.pop_front(); for (auto& [neighbor, weight] : graph[node]) { if (dist[neighbor] > dist[node] + weight) { dist[neighbor] = dist[node] + weight; if (weight == 0) { dq.push_front(neighbor); // 权重为0的边，加入队首 } else { dq.push_back(neighbor); // 权重为1的边，加入队尾 } } } } return dist; }【状态压缩BFS】当需要记录多个状态时，可以使用位运算进行状态压缩
// 使用位运算表示状态，比如在迷宫中记录已访问的物品 int bfsWithBitmask(vector<vector<int>>& grid, int startX, int startY) { int rows = grid.size(); int cols = grid[0].size(); int totalItems = 5; // 假设有5个物品需要收集 // visited[x][y][state]表示在(x,y)位置，已收集物品状态为state时是否访问过 vector<vector<vector<bool>>> visited(rows, vector<vector<bool>>(cols, vector<bool>(1 << totalItems, false))); queue<tuple<int, int, int>> q; // (x, y, state) q.push({startX, startY, 0}); visited[startX][startY][0] = true; int steps = 0; vector<pair<int, int>> dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; while (!q.empty()) { int size = q.size(); for (int i = 0; i < size; i++) { auto [x, y, state] = q.front(); q.pop(); // 如果所有物品都收集了 if (state == (1 << totalItems) - 1) { return steps; } for (auto& dir : dirs) { int nx = x + dir.first; int ny = y + dir.second; if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || grid[nx][ny] == -1) continue; int newState = state; if (grid[nx][ny] > 0) { // 收集物品，物品编号为grid[nx][ny]-1 newState |= (1 << (grid[nx][ny] - 1)); } if (!visited[nx][ny][newState]) { visited[nx][ny][newState] = true; q.push({nx, ny, newState}); } } } steps++; } return -1; // 无法收集所有物品 }
A*搜索算法（BFS的扩展）
A*算法是BFS的一种启发式扩展，它使用估价函数来引导搜索方向，优先探索更有希望到达目标的路径。
// A*算法寻找最短路径
vector<pair<int, int>> aStarSearch(vector<vector<int>>& grid, pair<int, int> start, pair<int, int> goal) {
int rows = grid.size();
int cols = grid[0].size();
// 优先队列，按f值（g+h）排序，最小值在队首
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
// g[r][c]表示从起点到(r,c)的已知最短距离
vector<vector<int>> g(rows, vector<int>(cols, INT_MAX));
// parent记录路径
vector<vector<pair<int, int>>> parent(rows, vector<pair<int, int>>(cols));
// 启发函数h：曼哈顿距离
auto h = [&goal](int r, int c) -> int {
return abs(r - goal.first) + abs(c - goal.second);
};
g[start.first][start.second] = 0;
pq.push({h(start.first, start.second), start.first, start.second}); // {f, r, c}
vector<pair<int, int>> dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
while (!pq.empty()) {
auto [f, r, c] = pq.top();
pq.pop();
// 达到目标
if (r == goal.first && c == goal.second) {
// 重建路径
vector<pair<int, int>> path;
for (auto pos = make_pair(r, c); pos != start; pos = parent[pos.first][pos.second]) {
path.push_back(pos);
}
path.push_back(start);
reverse(path.begin(), path.end());
return path;
}
// f值已经不是最小值，跳过
if (f > g[r][c] + h(r, c)) continue;
for (auto& dir : dirs) {
int nr = r + dir.first;
int nc = c + dir.second;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] == 1) continue;
int ng = g[r][c] + 1; // 假设步长为1
if (ng < g[nr][nc]) {
g[nr][nc] = ng;
parent[nr][nc] = {r, c};
pq.push({ng + h(nr, nc), nr, nc});
}
}
}
return {}; // 无法到达目标
}
练习题推荐
- LeetCode 934: 最短的桥（多源BFS）
- LeetCode 994: 腐烂的橘子（多源BFS模拟）
- LeetCode 1162: 地图分析（多源BFS计算距离）
- LeetCode 127: 单词接龙（变形BFS）
- LeetCode 752: 打开转盘锁（状态BFS）
- LeetCode 815: 公交路线（图的BFS）
- LeetCode 773: 滑动谜题（状态压缩BFS）
- POJ 3984: 迷宫问题（基础BFS路径记录）
- CodeForces 580C: Kefa and Park（带条件BFS）
总结
广度优先搜索是解决"最短路径"类问题的首选算法，尤其在无权图或等权图中。它的核心思想是"层次遍历"，确保首先探索距离起点近的节点，然后逐渐向外扩展。
BFS的关键优势：
- 保证找到的路径是最短的（在无权图中）
- 适合处理最短路径、最少步数等问题
- 能够有效处理大型状态空间
BFS的主要挑战：
- 空间复杂度高，需要存储整个前沿
- 在处理大型图或高维状态空间时，队列可能会变得很大
在竞赛编程中，熟练掌握BFS的变体（如双向BFS、A*搜索、01BFS等）能够帮助你高效解决各类搜索问题。