Python 对 BFS(广度优先算法)讲解
阅读本文大概需要 6 分钟。
概述
BFS 算法像是近视的小明的眼镜掉在了地上，小明肯定是先摸索离手比较近的位置，然后手慢慢向远方延伸，直至摸到眼镜，像是以小明为中心搜索圈不断扩大的过程。
通常用队列（先进先出，FIFO）实现
初始化队列Q；
Q = {起点s}；标记s为已访问；
while(Q非空):
取Q队首元素u；u出队；
if u == 目标状态 {...}
所有与u相邻且未被访问的点进入队列；
标记u为已访问；
如图所示：
实例讲解
“一马当先”
下过象棋的人都知道，马只能走'日'字形（包括旋转90°的日），现在想象一下，给你一个n行m列网格棋盘， 棋盘的左下角有一匹马，请你计算至少需要几步可以将它移动到棋盘的右上角，若无法走到，则输出-1. 如n=1，m=2,则至少需要1步；若n=1，m=3,则输出-1。
首先我们直接按照上面的程序流程来进行代码实现。
代码一：
from collections import deque
n = 3
m = 5
def steps_count2():
'''
BFS算法求解，广度优先搜索算法
通常用队列（先进先出，FIFO）实现
初始化队列Q；
Q = {起点s}；标记s为已访问；
while(Q非空):
取Q队首元素u；u出队；
if u == 目标状态 {...}
所有与u相邻且未被访问的点进入队列；
标记u为已访问；
:return:
'''
global m,n
dx = [-1, -2, -2, -1, +1, +2, +2, +1]
dy = [+2, +1, -1, -2, -2, -1, +1, +2]
v = {(x, y): False for x in range(0, n + 1) for y in range(0, m + 1)}
v[(0, 0)] = True
q = deque([(0, 0, 0)])
while len(q) > 0:
p = q.popleft()
for i in range(8):
x = p[0] + dx[i]
y = p[1] + dy[i]
if x < 0 or x > n or y < 0 or y > m:
continue
if v[(x, y)]:
continue
v[(x, y)] = True
q.append((x, y, p[2] + 1))
if x == n and y == m:
return p[2] + 1
return -1
元素定义
dx、dy 分别指的是棋子下一步移动的可能性，这里采用枚举的方法给出了所有符合规则的移动策略，根据 i 值获得不同的移动的策略。
v 表示 n 行 m 列的坐标图，其中设定 (0,0)为坐标起点（左下角的起点），(n,m)为坐标终点（即右上角的终点）。声明 v时，将每个坐标置为 False，即为未走过；将 v[(0,0)]置为起点，状态改为 True。
q 表示队列，初始值为(0,0,0)，其中前面两位指的是起点坐标，第三位指的是移动的步数。
p 表示从 q 左侧取出的第一个值，取出后并删除队列中的记录。
流程分析
从 q 中取值，得到 p(0,0,0)，q 暂时为空。遍历 dx,dy，选择(0,0)的移动的策略，将移动后的结果值(x,y)进行大小比较，若不合适，则更换移动策略。判断(x,y)状态值是否为 True，如果为 True，则跳过（因为避免兜圈，导致步数过大，我们要求的是最小步数）。设置(x,y)状态值为 True，步数（p[2]）加 1，放入队列中去。判断(x,y)与(n,m)是否相等，若相同则返回最小步数。
对(0,0)进行不同的移动后，获得的值都放入到 q 队列，接着对 q 队列进行取值判断。此时 q 队列值为[(2,1,1),(1,2,1)]，取出最左侧的值(2,1,1)，重复上述操作，最后 q 队列值为[(1,2,1),(3,3,2),(1,3,2),(0,2,2)]，依次类推，直到(x,y)与(n,m)值相同，则返回步数。
代码二：
n = 3
m = 5
def steps_count4():
global m, n
dx = [+2, +1, -1, -2, -2, -1, +1, +2]
dy = [-1, -2, -2, -1, +1, +2, +2, +1]
temp = [set(), set([(0, 0)]), set()]
t = 1
f = True
while f:
f = False
for loc in temp[1]:
for i in range(8):
x = loc[0] + dx[i]
y = loc[1] + dy[i]
if (x,y) == (m, n):
return t
elif x >= 0 and y >= 0 and x <= m and y <= n and not ((x,y) in temp[0] or (x,y) in temp[1] or (x,y) in temp[2]):
temp[2].add((x,y))
f = True
t += 1
del temp[0]
temp.append(set())
return -1
元素定义
temp：用来存储不同层的坐标，其中 temp[0] 表示上一层，temp[1] 表示当前层，temp[2] 表示下一层。
f：逻辑型值，用来记录是否有新的坐标被丢入 temp[2] 中。
t：用于记录层数。
流程解析
创建一个序列 temp=[[],[[0,0]],[]],分别表示上一层、当前层、下一层；
初始化 t=1，f=True；
若 f 为 True 进入以下流程，否则输出 -1；
令 f=False，依次遍历 temp[1] 里的每一个坐标，对每一个坐标采取全部 8 种移动方式，若移动到了 [m,n] 则输出层数 t；
若移动后仍在棋盘内且不存在 temp 里任何一层中，则将这个坐标加入到 temp[2] 中，且令 f=True；
遍历完成后，del temp[0] 以控制数据量，这个操作同时使 temp[1] 顶替temp[0]，temp[2] 顶替 temp[1]，然后使用 append 方法插入一个新的空序列作为 temp[2]，t+=1；
回到第三步并重复。