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

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

引用

CSDN

1.

https://blog.csdn.net/m0_73916791/article/details/134772126

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

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经典问题，详细介绍和解题思路：

1. 二叉树的层次遍历

在这个问题中，我们需要通过 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;
}

2. 岛屿的个数

给定一个由 ‘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;
}

3. 打开密码锁的最少步数

给你一个初始为 ‘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;
}

4. 图中两点间最短路径长度

给定一个无向图，求从起点 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];
}

5. 找到最近的医院

给定一个二维的 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 队列
  // 先把所有的医院节点放进队列，然后开始 BFS
  for(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;
}

6. 最小基因变异

给定两个基因序列 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;
}