广度优先搜索（BFS）算法精解：用C++探索层级遍历的奥秘

创作时间:

作者:

@小白创作中心

广度优先搜索（BFS）算法精解：用C++探索层级遍历的奥秘

引用

CSDN

https://m.blog.csdn.net/muzibuku/article/details/146171939

广度优先搜索（BFS）算法是一种在树或图中逐层遍历节点的算法，常用于解决最短路径和层级关系问题。本文将从BFS的基本原理、核心要素、经典应用场景、变种形式以及性能优化等多个方面进行深入解析，并通过C++代码示例帮助读者更好地理解和掌握BFS算法。

一、BFS的本质：层层递进的探索艺术

广度优先搜索（Breadth-First Search）如同水面涟漪般逐层展开，是解决最短路径和层级关系问题的核心算法。它通过队列数据结构实现O(n)时间复杂度的高效遍历，在树/图结构处理中展现出独特优势。我们将从三大经典应用场景展开解析：

二、BFS的核心三要素

2.1 算法框架模板

void BFS(Node* start) {
    queue<Node*> q;
    unordered_set<Node*> visited;
    
    q.push(start);
    visited.insert(start);
    
    while (!q.empty()) {
        int levelSize = q.size();  // 当前层节点数
        for (int i = 0; i < levelSize; ++i) {
            Node* cur = q.front(); q.pop();
            
            // 处理当前节点
            process(cur);
            
            // 扩展相邻节点
            for (Node* neighbor : cur->neighbors) {
                if (!visited.count(neighbor)) {
                    q.push(neighbor);
                    visited.insert(neighbor);
                }
            }
        }
    }
}

2.2 算法特性分析

维度	BFS特性	典型应用场景
遍历顺序	层级递增	最短路径问题
数据结构	队列（FIFO）	社交网络关系层级
空间复杂度	O(w)（w为最大宽度）	棋盘类游戏解法
时间复杂度	O(V+E)	网页爬虫层级抓取

三、基础应用：二叉树的层级遍历（LeetCode 102）

3.1 标准BFS实现

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int size = q.size();
        vector<int> level;
        
        for (int i = 0; i < size; ++i) {
            TreeNode* cur = q.front(); q.pop();
            level.push_back(cur->val);
            
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        
        res.push_back(level);
    }
    return res;
}
/* 输入：
    3
   / \
  9  20
    /  \
   15   7
输出：[[3], [9,20], [15,7]] */

算法亮点：

队列缓存当前层节点
层级尺寸预记录保证分组正确
自动处理空树边界情况

四、进阶应用：迷宫最短路径（LeetCode 1091）

4.1 多方向BFS扩展

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    int n = grid.size();
    if (grid[0][0] || grid[n-1][n-1]) return -1;
    
    queue<pair<int, int>> q;
    vector<vector<int>> dirs = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, 
                              {0,1}, {1,-1}, {1,0}, {1,1}};
    
    grid[0][0] = 1;  // 标记已访问
    q.emplace(0, 0);
    int steps = 1;
    
    while (!q.empty()) {
        int size = q.size();
        while (size--) {
            auto [x, y] = q.front(); q.pop();
            
            if (x == n-1 && y == n-1) return steps;
            
            for (auto& d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >=0 && nx <n && ny>=0 && ny <n && grid[nx][ny]==0){
                    grid[nx][ny] = 1;  // 提前标记避免重复入队
                    q.emplace(nx, ny);
                }
            }
        }
        steps++;
    }
    return -1;
}
// 输入：[[0,0,0],[1,1,0],[1,1,0]] → 输出：4（图示路径）

优化技巧：

8方向向量简化代码
原地修改矩阵替代额外存储
提前终止条件判断

五、BFS的四大变种形式

5.1 双向BFS（适用于已知起点终点）

int bidirectionalBFS(Node* start, Node* end) {
    unordered_set<Node*> visited;
    unordered_set<Node*> beginSet{start}, endSet{end};
    int steps = 0;
    
    while (!beginSet.empty() && !endSet.empty()) {
        if (beginSet.size() > endSet.size())
            swap(beginSet, endSet);  // 始终扩展较小集合
        
        unordered_set<Node*> tempSet;
        for (Node* cur : beginSet) {
            if (endSet.count(cur)) return steps + 1;
            visited.insert(cur);
            
            for (Node* neighbor : cur->neighbors) {
                if (!visited.count(neighbor))
                    tempSet.insert(neighbor);
            }
        }
        beginSet = tempSet;
        steps++;
    }
    return -1;
}

5.2 优先队列BFS（Dijkstra算法）

int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    vector<vector<pair<int, int>>> graph(n+1);
    for (auto& t : times)
        graph[t[0]].emplace_back(t[1], t[2]);
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    vector<int> dist(n+1, INT_MAX);
    
    pq.emplace(0, k);
    dist[k] = 0;
    
    while (!pq.empty()) {
        auto [time, node] = pq.top(); pq.pop();
        if (time > dist[node]) continue;
        
        for (auto& [v, w] : graph[node]) {
            if (dist[v] > time + w) {
                dist[v] = time + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    
    int maxTime = *max_element(dist.begin()+1, dist.end());
    return maxTime == INT_MAX ? -1 : maxTime;
}

六、性能优化与陷阱规避

6.1 常见性能陷阱

陷阱类型	错误示例	优化方案
重复节点入队	未记录已访问节点	使用哈希表/数组标记
无效路径扩展	不检查边界条件	提前验证坐标有效性
队列膨胀失控	过早标记导致路径丢失	入队时标记而非出队时
内存占用过高	存储完整路径信息	只记录必要状态信息

6.2 高级优化技巧

// 优化1：位压缩存储访问状态
uint64_t visited = 0;  // 适用于小规模状态存储
// 优化2：层级步数预计算
int steps = (q.size() && isTargetExist) ? preSteps + 1 : 0;
// 优化3：并行队列处理（OpenMP）
#pragma omp parallel for
for (int i = 0; i < q.size(); ++i) {
    // 并行处理相邻节点
}