图论广搜理论基础

广度优先搜索理论基础

深度优先搜索的讲解中,我们就讲过深度优先搜索和广度优先搜索的区别。

广搜(bfs)是一圈一圈的搜索过程,和深搜(dfs)是一条路跑到黑然后再回溯。

广搜的使用场景

广搜的搜索方式就适合于解决两个点之间的最短路径问题。

因为广搜是从起点出发,以起始点为中心一圈一圈进行搜索,一旦遇到终点,记录之前走过的节点就是一条最短路。

当然,也有一些问题是广搜 和 深搜都可以解决的,例如岛屿问题,这类问题的特征就是不涉及具体的遍历方式,只要能把相邻且相同属性的节点标记上就行。 (我们会在具体题目讲解中详细来说)

广搜的过程

上面我们提过,BFS是一圈一圈的搜索过程,但具体是怎么一圈一圈来搜呢。

我们用一个方格地图,假如每次搜索的方向为 上下左右(不包含斜上方),那么给出一个start起始位置,那么BFS就是从四个方向走出第一步。

图一

如果加上一个end终止位置,那么使用BFS的搜索过程如图所示:

图二

我们从图中可以看出,从start起点开始,是一圈一圈,向外搜索,方格编号1为第一步遍历的节点,方格编号2为第二步遍历的节点,第四步的时候我们找到终止点end。

正是因为BFS一圈一圈的遍历方式,所以一旦遇到终止点,那么一定是一条最短路径。

而且地图还可以有障碍,如图所示:

图三

在第五步,第六步 我只把关键的节点染色了,其他方向周边没有去染色,大家只要关注关键地方染色的逻辑就可以。

从图中可以看出,如果添加了障碍,我们是第六步才能走到end终点。

只要BFS只要搜到终点一定是一条最短路径,大家可以参考上面的图,自己再去模拟一下。

代码框架

大家应该好奇,这一圈一圈的搜索过程是怎么做到的,是放在什么容器里,才能这样去遍历。

很多网上的资料都是直接说用队列来实现。

其实,我们仅仅需要一个容器,能保存我们要遍历过的元素就可以,那么用队列,还是用栈,甚至用数组,都是可以的

用队列的话,就是保证每一圈都是一个方向去转,例如统一顺时针或者逆时针

因为队列是先进先出,加入元素和弹出元素的顺序是没有改变的。

如果用栈的话,就是第一圈顺时针遍历,第二圈逆时针遍历,第三圈有顺时针遍历

因为栈是先进后出,加入元素和弹出元素的顺序改变了。

那么广搜需要注意 转圈搜索的顺序吗? 不需要!

所以用队列,还是用栈都是可以的,但大家都习惯用队列了,所以下面的讲解用我也用队列来讲,只不过要给大家说清楚,并不是非要用队列,用栈也可以

下面给出广搜代码模板,该模板针对的就是,上面的四方格的地图: (详细注释)

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图,也就是一个二维数组
// visited标记访问过的节点,不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
    queue<pair<int, int>> que; // 定义队列
    que.push({x, y}); // 起始节点加入队列
    visited[x][y] = true; // 只要加入队列,立刻标记为访问过的节点
    while(!que.empty()) { // 开始遍历队列里的元素
        pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素
        int curx = cur.first;
        int cury = cur.second; // 当前节点坐标
        for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 坐标越界了,直接跳过
            if (!visited[nextx][nexty]) { // 如果节点没被访问过
                que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点
                visited[nextx][nexty] = true; // 只要加入队列立刻标记,避免重复访问
            }
        }
    }

}

以上模板代码,就是可以直接拿来做 200.岛屿数量 这道题目,唯一区别是 针对地图 grid 中有数字1的地方去做一个遍历。

即:

if (!visited[nextx][nexty]) { // 如果节点没被访问过

改为

if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') { // 如果节点没被访问过且节点是可遍历的

就可以通过 200.岛屿数量 这道题目,大家可以去体验一下。

总结

当然广搜还有很多细节需要注意的地方,后面我会针对广搜的题目还做针对性的讲解,因为在理论篇讲太多细节,可能会让刚学广搜的录友们越看越懵,所以细节方面针对具体题目在做讲解。

本篇我们重点讲解了广搜的使用场景,广搜的过程以及广搜的代码框架。

其实在二叉树章节的层序遍历中,我们也讲过一次广搜,相当于是广搜在二叉树这种数据结构上的应用。

这次则从图论的角度上再详细讲解一次广度优先遍历。

相信看完本篇,大家会对广搜有一个基础性的认识,后面再来做对应的题目就会得心应手一些。

其他语言版本

Python

from collections import deque

dir = [(0, 1), (1, 0), (-1, 0), (0, -1)] # 创建方向元素

def bfs(grid, visited, x, y):
  
  queue = deque() # 初始化队列
  queue.append((x, y)) # 放入第一个元素/起点
  visited[x][y] = True # 标记为访问过的节点
  
  while queue: # 遍历队列里的元素
  
    curx, cury = queue.popleft() # 取出第一个元素
    
    for dx, dy in dir: # 遍历四个方向
    
      nextx, nexty = curx + dx, cury + dy
      
      if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]): # 越界了,直接跳过
        continue
        
      if not visited[nextx][nexty]: # 如果节点没被访问过  
        queue.append((nextx, nexty)) # 加入队列
        visited[nextx][nexty] = True # 标记为访问过的节点