• 本文目录导读：
• 1、 BFS基础概念
• 2、 BFS代码实现
• 3、 BFS应用——迷宫问题
• 4、 总结

作为一个程序员，掌握算法是必备的技能之一。而广度优先搜索（BFS）是其中非常基础且常用的一种。本篇文章将以python语言为例，记录我学习BFS算法的过程和做题经验。

1. BFS基础概念

首先来了解一下什么是广度优先搜索。简单来说，就是从起点开始，按照“宽度”优先依次访问其相邻节点，并将这些节点按照访问顺序加入队列中；然后对于每个队列中的节点，再依次访问它们的相邻节点并加入队列中；直到找到目标节点或者遍历完所有可达路径。

接下来我们可以看一个简单的示意图：

![image-20211019131825498]()

从上图可以看出，我们首先从起点A开始遍历，然后在第一层扩展出了B和C两个相邻节点，并将其加入队列中；接着在第二层扩展出了D、E、F三个相邻节点，并将其加入队列中……如此往复，直到找到目标节点或者遍历完所有可达路径。

2. BFS代码实现

在python中，我们可以用一个队列来存储每一层的节点，并使用一个visited数组来记录每个节点是否已经被访问过。

具体实现代码如下：

“`python

def bfs(start, end):

queue = [(start, 0)]

visited = set()

visited.add(start)

while queue:

node, step = queue.pop(0) # 弹出队首元素

if node == end:

return step

for nei in neighbors(node): # 遍历相邻节点

if nei not in visited:

visited.add(nei)

queue.append((nei, step+1))

“`

其中，start和end分别代表起点和终点；queue是存储每一层节点的队列；visited是记录已访问过的节点的集合。neighbors函数是自定义函数，用于获取某个节点的相邻节点列表。

我们从起点开始遍历，并将其加入队列中。然后进入while循环，不断弹出队首元素并遍历其相邻未访问过的子结点。若发现某个子结点为终点，则返回当前步数；否则将该子结点加入队列并标记为已访问。最后如果遍历完所有可达路径仍未找到终点，则返回-1表示搜索失败。

3. BFS应用——迷宫问题

接下来我们来看一个BFS的应用——迷宫问题。假设有一个n*m的二维数组，其中0表示空地，1表示墙壁，9表示目标点。现在从起点(0, 0)出发，每次只能向上、下、左、右四个方向移动一格，请问最少需要几步才能到达目标点。

例如以下迷宫：

0 1 1 0

0 1 0 1

0 1 9 1

我们可以将其转化为一个二维矩阵，并使用BFS来解决这个问题。

代码实现如下：

def bfs(maze, start):

queue = [(start[0], start[1], 0)]

visited.add((start[0], start[1]))

x, y, step = queue.pop(0)

if maze[x][y] == ‘9’:

for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]:

nx = x + dx

ny = y + dy

if nx >= len(maze) or nx = len(maze[0]) or ny <

continue

if maze[nx][ny] == ‘1’ or (nx, ny) in visited:

visited.add((nx, ny))

queue.append((nx ,ny ,step+11))

return -11

其中maze是存储迷宫的二维矩阵；start是起点坐标。我们使用三元组(x, y, step)来表示队列中的每个节点，其中x和y分别表示当前节点的行和列，step表示到达该节点需要的步数。

在遍历相邻节点时，我们使用dx、dy来记录四个方向移动时所需偏移量，并计算出新位置nx、ny。然后判断该位置是否越界或者已经访问过或者是墙壁，若满足任一条件，则跳过该位置；否则将其加入队列并标记为已访问。

最后如果遍历完所有可达路径仍未找到目标点，则返回-1表示搜索失败。

4. 总结

本篇文章主要介绍了BFS算法的基础概念、代码实现以及应用场景，并通过一个简单的迷宫问题进行了实际演示。希望能对大家学习算法有所帮助。

最后总结一下BFS算法的特点：

1. 广度优先搜索可以求解最短路径问题。

2. 需要借助队列数据结构进行实现。

3. 适用于无权图（即边权都为1）。

4. 时间复杂度为O(N)，其中N为图中顶点数+边数。