资源简介

课时39 广度优先搜索算法
一、广度优先搜索（BFS）的基本概念
1. 概念：广度优先搜索（Breadth-First Search,BFS）是一种用于遍历或搜索树、图的算法。
2. 核心思想：逐层探索。从起点开始，先访问所有相邻节点，再依次访问下一层的节点。
3. 特点。
（1）队列数据结构：BFS 通常使用队列（先进先出）来管理待访问的节点。
（2）最短路径保证：在无权图中，BFS 能找到起点到所有可达节点的最短路径。
（3）层级遍历：按距离起点的层数依次访问节点。
1. 初始化：将起点加入队列，并标记为已访问。
2. 循环处理队列。
（1）取出队列中的第一个节点。
（2）遍历该节点所有未访问的邻接节点，将这些节点加入队列并标记为已访问。
3. 终止条件：当队列为空或找到目标节点时，遍历完成。
二、广度优先搜索的步骤
1.树的层级遍历。
（1）问题描述：按层输出二叉树的所有节点值。
（2）Python 实现。
class TreeNode: #定义二叉树类
def __init__(self,val=0,left=None,right=None):
self.val=val
self.left=left
self.right=right
def bfs_tree(root): #二叉树的层级遍历
if not root:
return []
queue=[root] #将根节点加入队列
result=[]
while queue: #循环处理队列
#记录当前层的节点数，确保按层输出
level_size=len(queue)
current_level=[]
for _ in range(level_size):
三、BFS 的经典问题与 Python 实现
#取出队列中的第一个节点
node=queue.pop(0)
#存入当前层级
current_level.append(node.val)
#将该节点的左、右孩子加入队列
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
root=TreeNode(1)
root.left=TreeNode(2)
root.right=TreeNode(3)
root.left.left=TreeNode(4)
root.right.right=TreeNode(5)
print(bfs_tree(root)) #输出：[[1],[2,3],[4,5]]
2.迷宫问题。
（1）问题描述：在二维矩阵表示的迷宫中，找到从起点到终点的最短路径（假设可通行区域为 0，障碍物为1）。
（2）Python 实现。
import queue
path=[]
def bfs(maze):
rows=len(maze) #迷宫行数（高）
cols=len(maze[0]) #迷宫列数（宽）
#方向数组：右、下、左、上
directions=[(0,1),(1,0),(0,-1),(-1,0)]
q=queue.Queue() #创建一个队列
q.put((0,0,-1)) #起点位置入队(行,列,指针)
mark=[[False for _ in range(cols)] for _ in range(rows)]
mark[0][0]=True #给当前位置做上标记
while not q.empty():
x0,y0,p=q.get() #从队列中出队一个位置
path.append((x0,y0,p)) #用于记录路径的链表
#如果到达右下角出口，则返回 True，结束探索
if x0==rows-1 and y0==cols-1:
return True
for d in directions: #探索四个方向
x,y=x0+d[0],y0+d[1] #探索新位置
#如果新位置不越界，为 0 且无标记
if 0<=xmaze[x][y]==0 and not mark[x][y]:
mark[x][y]=True
#新位置入队
q.put((x,y,len(path)-1))
#如果没有找到出口，则返回 False
return False
#迷宫数组（坐标轴 x 向下，y 向右）
maze=[[0,1,0,0,0,1],[0,1,0,0,0,1],
[0,0,0,0,0,1],[0,1,1,1,0,1],[0,0,0,0,0,0]]
if bfs(maze):
print("可以走出迷宫")
#从终点位置开始，倒着输出路径
p=len(path)-1
while p!=-1:
print((path[p][0],path[p][1]),end="<--")
p=path[p][2] #跳到下一个节点
else:
print("不可以走出迷宫")
'''输出：
可以走出迷宫
(4,5)<--(4,4)<--(3,4)<--(2,4)<--(2,3)<--(2,2)<--(2,1)<--(2,0)<--(1,0)<--(0,0)<--
'''
1. 概念：深度优先搜索（Depth First Search,DFS）是一种用于遍历树或图的算法。二叉树的前序遍历本质上就是深度优先搜索。回溯搜索是深度优先搜索的一种。
2. 核心思想：深度优先搜索通过递归的方式，深入探索每个可能的选择，直到达到某种结束条件，然后再回溯到前一个状态继续探索其他可能的路径。
3.BFS 与 DFS 的比较。
四、深度优先搜索（DFS）
特性
BFS
DFS
数据结构
队列（先进先出）
栈（后进先出）或递归
空间复杂度
较高（存储所有当前层节点）
较低（仅存储当前路径）
最短路径
保证找到最短路径（无权图）
不保证
适用场景
层级遍历、最短路径问题
拓扑排序、连通性问题、回溯问题
典例1　［2026浙东北联盟］n行m列的工厂网格中分布着不同能量值的资源块，机器人初始位于(x,y)，机器人可以上下左右方向移动收集四周的资源进行充电：
●机器人电量S为已收集资源块能量值之和。
●资源块能量值为k，当S的值为0或k　　现要求出机器人能获得的最大能量值。
　　如图a所示，机器人初始位置为(1,1)，获得能量9，可以向四个方向移动，其能量获取路径如图b所示。当能量S=28时，四周已无满足条件的资源块，行程结束。因此，获取的最大能量值为28。
请回答下列问题：
（1）若将图a中第一行(0,1)位置的能量值改为7，则机器人获取的最大能量值为　　　　　　　。
13
（2）insert函数功能为：在链表中插入值为[x,y,k]的资源块，并返回头指针。其中x，y为位置，k为能量值。实现上述功能的Python程序如下，请在画线处填入合适的代码。
def insert(h,x,y,k):
if h==-1:
que.append([x,y,k,-1])
h=len(que)-1
return h
que.append([x,y,k,-1])
pos=len(que)-1
if k<=que[h][2]:
que[pos][3]=h
　　　①　　　.
else:
p=h
q=que[p][3]
while 　　　②　　　:
p=q
q=que[q][3]
que[pos][3]=q;que[p][3]=pos
return h
h=pos　或　return pos
q!=-1 and que[q][2]if s==0 or s/2>top[2]:
　　　①　　　.
elif s/2<=top[2]:
return s
for i in range(len(dx)):
nx=top[0]+dx[i]
ny=top[1]+dy[i]
if nx>=n or nx<0 or ny<0 or ny>=m or vis[nx][ny]:
continue
h=　　　②　　　.
vis[nx][ny]=True
return s
（3）walk函数实现机器人收集资源块的过程，并返回获取的能量最大值。Python程序如下，请在画线处填入合适的代码。
def walk(x,y):
#dx,dy表示上下左右四个方向
dx=[0,0,-1,1]
dy=[-1,1,0,0]
que.append([x,y,data[x][y],-1])
s=0
h=0
vis[x][y]=True
while h!=-1:
top=que[h]
h=que[h][3]
s+=top[2]
insert(h,nx,ny,data[nx][ny])
'''
读取网格的行数、列数存入变量n、m。读取网格数据存入data列表，如图a所示，data列表为[[14,6,9],[4,9,20],[17,15,7]]。vis二维数组初始化为False，代码略
'''
x=y=1
que=[]
ans=walk(x,y)
print("最大能量值为：",ans)
胜券点拨1
明考向
本题主要考查广度优先搜索
审关键
向上下左右四个方向移动
考场思维快闪
（1）
若(0,1)位置的能量值改为7，机器人从(1,1)移动到(1,0)，能量值为9+4=13。此时7>13/2，四周已无满足条件的资源块，行程结束
（2）
①链表que中的节点按能量值升序排序，h为链表头指针，pos为当前资源块索引。若当前资源块能量值小于等于头节点能量值，则在链表头节点前插入，插入完成后，需要更新头指针。②若当前资源块能量值大于头节点能量值，则需要遍历链表查找插入位置，循环条件为当前节点q存在且其能量值小于新节点的能量值k
（3）
①当机器人满足收集条件时（电量s为0或资源块能量值小于s/2），收集资源块并更新电量s。②for循环遍历四个方向，判断机器人是否可移动，对于每个未访问的相邻位置(nx,ny)，需要将其插入链表并更新头指针h
典例 2 ［2025 稽阳联考］小明同学设计了一个模拟跳棋的算法。在一个矩形区域内，有若干棋子，初始位置在 0~1 行，现要将某棋子移动到完成线之后（完成线在 5~6 行之间）。规定：棋子一次移动可以连续跳跃或爬动 1 格（落点位置必须为空），方向只能纵向前进。其中 2~5 行有若干固定障碍物。当跳跃时，其他棋子和障碍物均可作为支撑点跳跃到对称位置，但中间不能有其他障碍物或棋子。若移动后落点在完成线之后，统一设置落点为 6 行且忽略落点是否为空。每颗棋子有唯一编号，跳跃时选择能跳最远距离的棋子（若距离相同，则选择编号最小的棋子），爬动时选择编号最小的可爬动棋子，直到全部棋子移动完成。
例如，如图所示的 4 号棋子一次移动经[3,2]后继续跳到[7,2]，因为[7,2]在
完成线之后，所以设置落点为[6,2]，完成移动。请回答下列问题：
（1）如图所示，3 号棋子需要移动　　　　　　　（填数字）次，才能移动
到[6,1]。
2
（2）定义函数 jump(qp,now)，功能是判断 now 位置的棋子是否可跳跃，now 为坐标，例如 4 号棋子在图中坐标为[1,2]。请在画线处填入合适的代码。
def jump(qp,now):
t1=now[0]+1;t2=now[1];t=1
while t1<6:
if qp[t1][t2]==0:
t1+=1;t+=1
else: #找到支撑点
if t1+t>5:
last=6
else:
last=　　　　　　　1
for i in range(t1+1,last+1):
#若路上有第二个障碍物
if qp[i][t2]>0:
return 0
else: #返回实际跳跃距离
return min(2*t,last-now[0])
return 0
t1+t
（3）实现上述功能的部分 Python 程序如下，请在画线处填入合适的代码。
def find(qp,t):
'''寻找编号为 t 的棋子，返回坐标如[2,3]或 False，代码略'''
def findmove(qp):
'''寻找编号最小的可爬动棋子，返回坐标如[2,3]，代码略'''
'''生成 8 行 4 列的棋盘数组 qp，其中 4 颗棋子依次编号为 1~4，障碍物编号为 9，代码略'''
c=0
while c<4:
max=0
for i in range(4):
now=find(qp,i+1)
if now!=False:
t=jump(qp,now)
tmp=　　　①　　　1
while t>0:
tmp=[tmp[0]+t,tmp[1]]
t=jump(qp,tmp)
if tmp[0]-now[0]>max:
n2=now
max=tmp[0]-now[0]
maxi=i+1
if max==0: #爬动
t=findmove(qp)
i=t[0];j=t[1]
　　　②　　　1
print(qp[i+1][j],"号",i,j,"→",i+1,j)
qp[i][j]=0
if i==5: #完成移动
c+=1
else: #跳跃
qp[n2[0]][n2[1]]=0
　　　③　　　=maxi
if n2[0]+max>5: #完成移动
c+=1
print("所有棋子均已进入目标区域，游戏结束！")
now
qp[i+1][j]=qp[i][j]
qp[n2[0]+max][n2[1]]
胜券点拨2
明考向
本题主要考查广度优先搜索算法的应用
审关键
通过BFS遍历棋子的所有可能移动路径
考场思维快闪
（1）
3号棋子从[1,1]位置出发，经过连续跳跃，先跳至[3,1]，再跳至[5,1]，再经过爬动到达[6,1]位置，共移动2次
（2）
根据代码可知，t1和t2从now位置出发，不断纵向前进，t记录now位置到支撑点的距离，当t1位置为支撑点时（qp[t1][t2]!=0），可以尝试跳跃到对称位置，则跳跃终点为t1+t
（3）
①for循环遍历所有棋子，当前棋子的位置为now，然后调用jump函数返回跳跃距离存入t中，tmp存储跳跃后棋子所在的位置，while循环判断tmp位置的棋子能否继续跳跃，将最大跳跃距离存储在max，对应棋子编号存储在maxi，故填入代码为now。②将编号最小的可爬动棋子的位置存入t，从坐标[i,j]爬动到[i+1,j]，故填入代码为qp[i+1][j]=qp[i][j]。③若max不为0，则选择编号为maxi的棋子进行跳跃，跳跃距离为max，棋子初始位置为n2，因此跳跃后qp[n2[0]][n2[1]]变为0，最后跳至的位置变为该棋子的编号，故填入代码为qp[n2[0]+max][n2[1]]
1.［2025丽水联考］小王编写了一段Python程序，帮助象棋初学者熟悉规则。输入某棋子的名称t及其当前位置(a,b)、目标位置(x,y)，程序根据t棋子的移动规则判断是否可以从(a,b)直接移动到(x,y)，并输出相应提示信息。棋盘坐标体系和部分棋子的移动规则如下：
①棋盘上有10条横线、9条竖线及90个交叉点，坐标体系如图a所示，(0,0)在左上角，则A处坐标为(2,3)。
②“马”的移动规则是“马走日”，先沿上、下、左或右的方向移动一步，再沿对角线移动一步。如图b中的“马”，可从所在位置直接移动到①~⑧中的一个位置，如果在A、B、C或D处遇到棋子，则不能移动，俗称“蹩马腿”。例如，若B处有棋子，则“马”不能直接移动到③或④。
③“车”的移动规则是“车走直路”，沿着上、下、左或右的方向直线前进，直到遇上其他棋子。如图c中的“车”，可以直接移动到A，但不能直接移动到B。
（1）当前棋盘状态如图a所示，若B处为“马”，则该棋子的坐标为
　　　　　　　，若A、C和D处均有棋子，则该棋子（马）可以直接移到的位置有
　　 　　（填数字）个。
(5,1)
4
（2）小王编写的部分Python程序如下，请在画线处填入合适的代码。
def ma(a,b,x,y):　#“马”的移动
if d[x][y]==1:
return "不能到达，目标位置有我方棋子"
if abs(x-a)==2 and abs(y-b)==1 or
　 ①　　　:
'''分析目标位置在该棋子下方的情况'''
if x-a==2:
if d[a+1][b]!=0:
return "不能到达目标位置，存在蹩马脚"
else:
return "可以到达目标位置"
'''分析目标位置在该棋子上方、左方、右方的情况，代码略'''
else:
return "不能到达目标位置"
def zulan(a,b,x,y):
#分析目标位置在该棋子下方的情况
if x>a:　
for i in range(x-a-1):
if 　　　②　　　:
return "不能到达目标位置，存在阻挡的棋子"
'''分析目标位置在该棋子上方、左方、右方的情况，代码略'''
if d[x][y]==1:
return "不能到达，目标位置有我方棋子"
if d[x][y]==2:
return "可以到达目标位置，并吃掉该位置的敌方棋子"
return "可以到达目标位置"
def ju(a,b,x,y):　#“车”的移动
if x==a or y==b:
return 　　　③　　　1
else:
return "不能到达目标位置"
abs(x-a)==1 and abs(y-b)==2
d[i+a+1][b]!=0 或　d[i+a+1][b]>0
zulan(a,b,x,y)
#主程序
'''读取棋盘当前状态的数据，存储到数组d中（如图d所示），其中0表示无棋子，1表示我方棋子，2表示对方棋子，代码略'''
for i in range(len(d)):　#输出当前棋盘状态
print(d[i])
while True:
t=input("请输入棋子名称：")
#获取起始位置坐标
a,b=map(int,input("请输入该棋子的起始位置：").split())
#获取目标位置坐标
x,y=map(int,input("请输入该棋子的目标位置：").split())
if t=="马":
print(ma(a,b,x,y))
elif t=="车":
print(ju(a,b,x,y))
#判断其他棋子的移动，代码略
（1）B处棋子的坐标为(5,1)。若A、C和D处均有棋子，根据“马”的移动规则，可以直接移到的位置有(3,0)、(3,2)、(7,2)、(7,0)。　（2）①abs(x-a)==2 and abs(y-b)==1表示一种“马走日”的情况，即“马”沿垂直方向走两格，水平方向走一格。另一种情况是沿水平方向走两格，垂直方向走一格，故填入代码为abs(x-a)==1 and abs(y-b)==2。②判断“车”从当前位置(a,b)向下方移动时，是否存在其他棋子阻拦，故填入代码为d[i+a+1][b]!=0或d[i+a+1][b]>0。③若目标位置在当前位置的正上、下、左或右的方向，则调用zulan(a,b,x,y)函数判断是否有棋子阻拦。
2.走迷宫游戏。现有一张由n×n个格子组成的迷宫地图，四面是墙，内部有随机出现的墙阻断通路，如图a所示是一张10×10规模的迷宫地图，白色方块代表可通行，黑色方块代表墙，不可通行。若将黑色方块用1表示，白色方块用0表示，则该迷宫可以转换成如图b所示的二维列表maze。现给定入口位置(x1,y1)和出口位置(x2,y2)，找到一条走出迷宫的最短路线，并输出该路线；若找不到则输出“迷路了！”。具体算法如下：
①从入口位置出发，向四个方向（按右、左、上、下的顺序）同时搜索线路，将搜索到的格子位置按序入队，一旦有一条线路率先到达出口，即为最短路线，游戏胜利；若走进死胡同，游戏失败。
②搜索过程中，为了防止走回头路，将走过的位置标记为2。同时为了回溯输出搜索到的最短路线，需要记录每一格子的前一格子下标位置。
例如，图a所示的地图中，入口位置为(1,1)，出口位置为(3,8)，最短路线为：[1,1]→[1,2]→[2,2]→[3,2]→[3,3]→[3,4]→[2,4]→[2,5]→[2,6]→[3,6]→[3,7]→[3,8]。
请回答下列问题：
（1）若迷宫地图如图a所示，入口位置为(1,2)，出口位置为(5,2)，则输出的最短路线为：[1,2]→ 　　　　　 　　→[5,2]。
[1,1]→[2,1]→[3,1]→[4,1]→[5,1]
（2）定义如下print_f(path)函数，功能是输出最短路线。
def print_f(path):
cur=path[-1]
realpath=[]
while cur[2]!=-1:
realpath.append([cur[0],cur[1]])
cur=path[cur[2]]
realpath.append([cur[0],cur[1]])
print("找到的最短路线如下：")
for line in range(len(realpath)-1,0,-1):
print(realpath[line],end="→")
print(realpath[0])
下列与虚线框内代码功能相同的是
　　 　（单选）。
A.cur=path[-1]
realpath=[[cur[0],cur[1]]]
while cur[2]!=-1:
cur=path[cur[2]]
realpath.append([cur[0],cur[1]])
B.cur=path[-1][2]
realpath=[]
while cur!=-1:
realpath.append([path[cur][0],
path[cur][1]])
cur=path[cur][2]
A
（3）实现探索最短路线功能的部分Python程序如下，请在画线处填入合适代码。
def maze_path_queue(x1,y1,x2,y2):
#方向：右、左、上、下
dirs=[[0,1],[0,-1],[-1,0],[1,0]]
que=[[]]*1000　#假设队列空间足够
head=tail=0
que[tail]=[x1,y1,-1]
tail+=1
path=[]
while 　　　①　　　:
cur=que[head]
head+=1
　　　②　　　1
if cur[0]==x2 and cur[1]==y2:
print_f(path)
return True
for k in dirs:
x_next=cur[0]+k[0]
y_next=cur[1]+k[1]
if maze[x_next][y_next]==0:
maze[x_next][y_next]=2
　　　③　　　1
tail+=1
#while循环正常结束后，执行该部分语句
else:　
print("迷路了！")
return False
'''
初始化二维列表maze模拟迷宫地图；
读取入口位置(x1,y1)及出口位置(x2,y2)；
代码略
'''
#主程序
maze_path_queue(x1,y1,x2,y2)
tail!=head　或　headpath.append(cur)
que[tail]=[x_next,y_next,len(path)-1]
（1）首先起点[1,2]入队，然后出队[1,2]，将可行方向的格子（[1,1]、[2,2]）依次入队；然后出队[1,1]，入队[2,1]；出队[2,2]，入队[3,2]；出队[2,1]，入队[3,1]；出队[3,2]，入队[3,3]；出队[3,1]，入队[4,1]；出队[3,3]，入队[3,4]；出队[4,1]，入队[5,1]；出队[3,4]，入队[2,4]；出队[5,1]，入队[5,2]、[6,1]；出队[2,4]，入队[2,5]、[1,4]；出队[5,2]，到达终点，回溯路径，得到最短路线为[1,2]→[1,1]→[2,1]→[3,1]→[4,1]→[5,1]→[5,2]。　（2）虚线框内代码的功能是将最短路径逆序添加到列表realpath中，选项B的代码从最后一个位置的前一个位置开始，逆序添加到realpath，因此结果中会缺失最后一个位置。　（3）①当队列不为空时，出队队首元素，故填入代码为tail!=head或head

展开更多......