利用Python实现广度优先搜索BFS

利用Python实现广度优先搜索BFS

广度优先搜索和深度优先搜索一样，都是最基础的搜索算法，为了体验广度优先搜索BFS的特点，在这篇文章中，我将使用Python来实现一个BFS解答题目的过程。

首先，让我们来看看BFS的定义：
广度优先搜索BFS（Breadth First Search）也称为宽度优先搜索，它是一种先生成的结点先扩展的策略。

其中，BFS的基本步骤有三步：
（1）从队列头取出一个结点，检查它按照扩展规则是否能够扩展，如果能，则生成一个新结点。
（2）检查新生成的结点，看它是否已经使用过，如果已经使用过，则放弃这个结点，然后回到第（1）步。否则，如果新结点第一次出现，就将它加入到队列尾。
（3）检查新结点是否目标结点。如果新结点是目标结点，则搜索成功，程序结束；若新结点不是目标结点，则回到第（1）步，再从队列头取出结点进行扩展。

具体步骤如下图所示：

下面，让我以LEETCODE的一个题目为例，用BFS的思路来解决这个问题：

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。

至于答案，我先贴代码，之后再来讲解：

a = [[0, 0, 0], [0, 1, 0], [1, 1, 1]]


def BFS_1(mat):
    m, n = len(mat), len(mat[0])  # 注意这里 m 为行数， n 为列数

    verify_mat = [[False for _ in range(n)] for _ in range(m)]  # 用于记录是否使用过该节点 矩阵

    res = [[None for _ in range(n)] for _ in range(m)]  # 用于记录结果 矩阵

    q = []  # 创建一个队列， 用于储存 待扩展的点

    for i in range(m):
        for j in range(n):
            if mat[i][j] == 0:
                verify_mat[i][j] = True  # 标记为已经访问过
                res[i][j] = 0  # 结果标记为 0
                q.append([i, j])  # 放入待扩展的队列

    while q:
        x, y = q.pop(0)  # 取出队列头的扩展点
        for x_bias, y_bias in [[0, 1], [0, -1], [1, 0], [-1, 0]]:  # 可以向四个方向扩展
            new_x = x + x_bias
            new_y = y + y_bias
            if 0 <= new_x < m and 0 <= new_y < n and verify_mat[new_x][new_y] == False:  # 判断扩展点有效性
                res[new_x][new_y] = res[x][y] + 1  # 新扩展点距离0的距离 为 原来点的距离+1
                verify_mat[new_x][new_y] = True  # 标记为已访问过
                q.append([new_x, new_y])  # 将新扩展的点加入队列
    return res

我来简单复述一下思路，使用Python来实现一个BFS的主要步骤如下：
1.创建一个矩阵/队列，来记录点是否被使用过；
2.创建一个队列，用于储存待扩展的点；
3.将第一批待扩展点加入2中的队列；
4.利用边界条件和具体约束条件作为约束，开始扩展点。

而上述代码中的 while q: 这一个循环模块，则是Python中实现BFS的经典模块了，基本所有与BFS有关的需求，都需要类似的代码。而每次我们需要调整的，就只有 if 这一行的约束条件了。

当然，为了让代码方便读，我才写了上面的代码，接下来，我们可以从两点进行优化：
1.验证矩阵和结果矩阵可以化为同一个矩阵，减少空间复杂度；
2.创建队列时可以使用 collections模块，减少时间复杂度。

以下是优化后的代码：

import collections

a = [[0, 0, 0], [0, 1, 0], [1, 1, 1]]

def BFS_2(mat):
    m, n = len(mat), len(mat[0])  # 注意这里 m 为行数， n 为列数

    res = [[None for _ in range(n)] for _ in range(m)]  # 用于记录结果 矩阵

    q = collections.deque()  # 使用collection库 设定一个 queue 来存储每个层次上的点，当然，用一般的[]来创建队列也行

    for i in range(m):
        for j in range(n):
            if mat[i][j] == 0:
                res[i][j] = 0  # 结果标记为 0
                q.append([i, j])  # 放入待扩展的队列

    while q:
        x, y = q.popleft()  # 取出队列头的扩展点
        for x_bias, y_bias in [[0, 1], [0, -1], [1, 0], [-1, 0]]:  # 可以向四个方向扩展
            new_x = x + x_bias
            new_y = y + y_bias
            if 0 <= new_x < m and 0 <= new_y < n and res[new_x][new_y] == None:  # 判断扩展点有效性
                res[new_x][new_y] = res[x][y] + 1  # 新扩展点距离0的距离 为 原来点的距离+1
                q.append([new_x, new_y])  # 将新扩展的点加入队列
    return res

当然，针对不同的题型，空间优化的方法不同，需要具体分析。
而对于collections模块为什么比一般的Python队列要快，我将会在以后的博客中更新。

以上是本人对BFS的个人理解，如有不对，欢迎指正！