当前位置：首页 > news >正文

一文弄懂BFS【广度优先搜索(Breadth-First Search)】

news 2025/8/22 2:25:12

在这里插入图片描述

BFS，全名为广度优先搜索(Breadth-First Search)，是一种用于图或树的遍历或搜索的算法。它的主要思想是由节点自身开始向它的邻居节点新进展开搜索，因此也常被形象地称为“层序遍历”。

BFS 基本思想

BFS 工作原理是，从开始节点开始，在访问节点的邻居节点之前，我们先访问其它节点。换句话说，我们旧基于当前层次来遍历节点，然后移至下一层再遍历节点。BFS 是以一种队列（Queue）结构的方式运行的，首先我们有一个包含开始节点的队列，然后：

- 我们从队列的前端取出一个节点
- 为了防止回溯和重复访问，我们会标记取出的节点为已访问
- 针对取出的节点，把尚未访问过的邻居节点全部加入队列
- 我们重复以上步骤，直至队列为空

通过以上步骤，你将会发现，你在访问节点的时候，首先访问的是距离开始节点最近的节点（层次最低的节点），然后层次逐渐提升，这就是 BFS 的特性。

BFS 伪代码模板

BFS 主要应用于树和图结构的遍历，因此伪代码也大致分为对应的两类（以下都是基于未标记图进行的操作）：

树的广度优先搜索

function BFS(root) {initialize queue;queue.push(root);while(!queue.empty()) {node = queue.front();queue.pop();process(node); //处理节点nodes = generate_related_nodes(node); //获取与节点相关的未访问过的子节点queue.push(nodes);}
}

图的广度优先搜索

function BFS(graph, start) {initialize queue and visited set;queue.push(start);visited.insert(start);while(!queue.empty()) {node = queue.front();queue.pop();process(node); //处理节点nodes = generate_related_nodes(node); //获取与节点相关的邻居节点for(node in nodes) {if(node not in visited) { //如果邻居节点尚未访问过queue.push(node);visited.add(node);}}}
}

接下来举出六个BFS经典问题，详细介绍和解题思路：

二叉树的层次遍历

在这个问题中，我们需要通过 BFS 遍历二叉树的每一层，以二维数组的形式返回结果。

vector<vector<int>> levelOrder(TreeNode* root) {if (!root) return {};vector<vector<int>> result;queue<TreeNode*> q;q.push(root);while (!q.empty()) {vector<int> one_level;for (int i = q.size(); i > 0; i--) {TreeNode* node = q.front();q.pop();one_level.push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}result.push_back(one_level);}return result;
}

岛屿的个数

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。

解题思路主要是遍历二维数组，当遇到 ‘1’ 时，通过 BFS 搜索并 ‘感染’ 周围的 ‘1’，最后计算 ‘1’ 的个数。

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};void bfs(vector<vector<char>>& grid, int x, int y, int row, int col) {queue<pair<int, int>> q;q.push({x, y});grid[x][y] = '0';  // 把 '1' 感染为 '0'while (!q.empty()) {auto [r, c] = q.front();q.pop();for (int i = 0; i < 4; ++i) {int nx = r + dx[i], ny = c + dy[i];if (nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] == '1') {q.push({nx, ny});grid[nx][ny] = '0';}}}
}int numIslands(vector<vector<char>>& grid) {int row = grid.size();if (row == 0) {return 0;}int col = grid[0].size();int res = 0;for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {if (grid[i][j] == '1') {bfs(grid, i, j, row, col);++res;  // 计算岛屿数量}}}return res;
}

打开密码锁的最少步数

给你一个初始为 ‘0000’ 的四位密码，你可以每次对密码的任意一位做上下旋转：旋转一次可以将该位的数字增加 1 或减少 1 。求出最少的旋转次数，使得密码等于 target 。

int openLock(vector<string>& deadends, string target) {unordered_set<string> dead(deadends.begin(), deadends.end());if (dead.count("0000")) return -1;if (target == "0000") return 0;unordered_map<string, int> dist{{"0000", 0}};queue<string> q;q.push("0000");while (!q.empty()) {string t = q.front(); q.pop();for (int i = 0; i < 4; i++) {for (int j = -1; j <= 1; j += 2) {string str = t;str[i] = (str[i] - '0' + j + 10) % 10 + '0';if (str == target) return dist[t] + 1;if (!dead.count(str) && !dist.count(str)) {dist[str] = dist[t] + 1;q.push(str);}}}}return -1;
}

图中两点间最短路径长度

给定一个无向图，求从起点 s 到终点 t，最短路径长度是多少。

vector<unordered_set<int>> g; // 图
unordered_map<int, int> dist; // 从起点到每个点的距离int bfs(int s, int t) {queue<int> q;q.push(s);dist[s] = 0;while (!q.empty()) {int x = q.front(); q.pop();for (int y : g[x]) {if (!dist.count(y)) {dist[y] = dist[x] + 1;q.push(y);}}}return dist[t];
}

找到最近的医院

给定一个二维的 0-1 矩阵，1 表示医院，0 表示型房屋。求每个房屋距离最近医院的距离。

vector<vector<int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};vector<vector<int>> findNearestHospital(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> dist(m, vector<int>(n, INT_MAX));queue<pair<int, int>> q;// BFS 队列// 先把所有的医院节点放进队列，然后开始 BFSfor(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid[i][j] == 1) {dist[i][j] = 0;q.push({i, j});}}}while(!q.empty()) {auto cur = q.front(); q.pop();for(auto dir : dirs) {int nx = cur.first + dir[0], ny = cur.second + dir[1];if(nx >= 0 && ny >= 0 && nx < m && ny < n) {if(dist[nx][ny] > dist[cur.first][cur.second] + 1) {dist[nx][ny] = dist[cur.first][cur.second] + 1;q.push({nx, ny});}}}}return dist;
}

最小基因变异

给定两个基因序列 start 和 end，一个基因库表 bank，求出把 start 变到 end 所需要的最小变异次数。一次基因变化代表改变一个字母。

int minMutation(string start, string end, vector<string>& bank) {unordered_set<string> dict(bank.begin(), bank.end());if (!dict.count(end)) return -1;unordered_map<string, int> dist{{start, 0}};queue<string> q;q.push(start);while (!q.empty()) {string gene = q.front(); q.pop();if (gene == end) return dist[gene];for (int i = 0; i < gene.size(); i++) {string newGene = gene;for (char c : "ACGT") {newGene[i] = c;if (dict.count(newGene) && !dist.count(newGene)) {dist[newGene] = dist[gene] + 1;q.push(newGene);}}}}return -1;
}